package edu.columbia.cs.cs1007.datastructures;
import java.util.InputMismatchException;
import java.util.LinkedList;
import java.util.Stack;
/**
* A Shunting Yard parser of arithmetic expressions.
* Supports +, -, * and / operators.
* @author Julia Stoyanovich
* COMS 1007, Summer 2009
*/
public class ShuntingYardEvaluator {
private String[] _expression;
private Stack<String> _stack;
private LinkedList<String> _queue;
/**
* Constructs an evaluator.
*
* @param anExpression - an array of Strings
*
*/
public ShuntingYardEvaluator(String anExpression) {
_expression = anExpression.split(" ");
_stack = new Stack<String>();
_queue = new LinkedList<String>();
}
/**
* Check whether the token is a supported operator.
* @param token
* @return true if operator, false otherwise
*/
public boolean isOperator(String token) {
return token.equals("+") || token.equals("-") || token.equals("*") || token.equals("/");
}
/**
* Check whether the token is an open parenthesis.
* @param token
* @return true if token is "(", false otherwise
*/
public boolean isOpenParen(String token) {
return token.equals("(");
}
/**
* Check whether the token is a closed parenthesis.
* @param token
* @return true if token is ")", false otherwise
*/
public boolean isClosedParen(String token) {
return token.equals(")");
}
/**
* Check whether the token is a positive integer.
* @param token
* @return
*/
public boolean isOperand(String token) {
boolean flag = false;
try {
int i = Integer.parseInt(token);
if (i>=0) {
flag = true;
}
} catch (NumberFormatException e) {
// noting, flag stays false
}
return flag;
}
/**
* Compare precedence of two operators.
* @param o1
* @param o2
* @return 0 if equal precedence,
* -1 if o1 has lower precedence,
* 1 if o1 has higher precedence
*/
public int comparePrecedence(String o1, String o2) {
if (o1.equals("+") || o1.equals("-")) {
if (o2.equals("+") || o2.equals("-")) {
return 0;
}
if (o2.equals("*") || o2.equals("/")) {
return -1;
}
}
if (o1.equals("*") || o1.equals("/")) {
if (o2.equals("+") || o2.equals("-")) {
return 1;
}
if (o2.equals("*") || o2.equals("/")) {
return 0;
}
}
// this is never called
return 0;
}
/**
* Transform an infix expression into postfix notation.
* Place result onto the queue.
*/
public void parse() {
for (String token : _expression) {
if (isOperand(token)) {
_queue.addLast(token);
} else if (isOperator(token)) {
// while we have an operator at the top of the stack
// that has higher or equal precedence than current token,
// pop the operator
while (!_stack.isEmpty() &&
isOperator(_stack.peek()) &&
(comparePrecedence(token, _stack.peek()) <= 0)) {
_queue.addLast(_stack.pop());
}
_stack.push(token);
} else if (isOpenParen(token)) {
_stack.push(token);
} else if (isClosedParen(token)) {
while (!isOpenParen(_stack.peek())) {
_queue.addLast(_stack.pop());
}
if (_stack.isEmpty()) {
throw new InputMismatchException("Unclosed right parenthesis");
}
// pop the left parent off the stack
_stack.pop();
} else {
throw new InputMismatchException("Invalid token: " + token);
}
}
// move the final result off the stack into the output queue
while (!_stack.isEmpty()) {
if (isOpenParen(_stack.peek()) || isClosedParen(_stack.peek())) {
throw new InputMismatchException("Unclosed parenthesis");
}
_queue.addLast(_stack.pop());
}
}
/**
* Generate a string representation of the queue.
* @return string representation
*/
public String queueToString() {
StringBuffer res = new StringBuffer();
for (String token : _queue) {
res.append(" " + token);
}
return res.toString();
}
public static void main(String[] args) {
ShuntingYardEvaluator eval = new ShuntingYardEvaluator(args[0]);
eval.parse();
System.out.println(eval.queueToString());
}
}
|