Algorithms
Convert to Reverse Polish Notation and Evaluate the Expression – Shunting-yard Algorithm
Given an infix expression with binary operators convert it to reverse polish notation (RPN) and evaluate the expression.
For example, the RPN form of the expression 3+2 is 32+. Similarly RPN for 3+4*2/(1-5)*2/3 is 342*15-/2*3/+ and the value of the expression is 1.66.
We can convert an infix expression to a reverse polish notation expression by using Shunting-yard algorithm developed by Dijkstra. This is a O(n) time and O(n) space algorithm.
Shunting-yard Algorithm
• While there are tokens to be read:
• Read a token.
• If the token is a number, then add it to the output queue.
• If the token is a function token, then push it onto the stack.
• If the token is a function argument separator (e.g., a comma):
• Until the token at the top of the stack is a left parenthesis, pop operators off the stack onto the output queue. If no left parentheses are encountered, either the separator was misplaced or parentheses were mismatched.
• If the token is an operator, o1, then:
• while there is an operator token, o2, at the top of the operator stack, and either
o1 is left-associative and its precedence is less than or equal to that of o2, or
o1 is right associative, and has precedence less than that of o2,
then pop o2 off the operator stack, onto the output queue;
• push o1 onto the operator stack.
• If the token is a left parenthesis (i.e. "("), then push it onto the stack.
• If the token is a right parenthesis (i.e. ")"):
• Until the token at the top of the stack is a left parenthesis, pop operators off the stack onto the output queue.
• Pop the left parenthesis from the stack, but not onto the output queue.
• If the token at the top of the stack is a function token, pop it onto the output queue.
• If the stack runs out without finding a left parenthesis, then there are mismatched parentheses.
• When there are no more tokens to read:
• While there are still operator tokens in the stack:
• If the operator token on the top of the stack is a parenthesis, then there are mismatched parentheses.
• Pop the operator onto the output queue.
•Exit.
For example, the expression A+B*C-D can be converted to RPN form as follows (example taken from wiki) –
Below is the implementation of the algorithm that runs in O(n) time.
public static ArrayList<String> convertInfix(String[] exprTokens){
ArrayList<String> infix = new ArrayList<String>();
Stack<String> operatorStack = new Stack<String>();
for(String op : exprTokens){
op = op.trim();
//if its an operand , simply append to output
if(!isOperator(op)){
infix.add(op);
}
//if its an operator
else{
//if its a left parenthesis then push it to stack
if(op.equals("(")){
operatorStack.push("(");
}
//other wise if it is a right parenthesis then pop the stack untill we see a matching left parenthesis
else if(op.equals(")")){
while(!operatorStack.peek().equals("(") && !operatorStack.isEmpty()){
infix.add(operatorStack.pop());
}
//if we do not have a matching left parethesis then it's a malformed expression
if(operatorStack.isEmpty() || !operatorStack.peek().equals("(")){
return null;
}
//otherwise we found a matching left. Just pop it out
else{
operatorStack.pop();
}
}
//otherwise its an operator
else{
//keep poping out element from stack and append in output as long as we see a higher precedence operator
//in the top of stack
while(
!operatorStack.isEmpty()
&& (
(isLeftAssociative(op) && getPrecedence(op) <= getPrecedence(operatorStack.peek()))
|| (!isLeftAssociative(op) && getPrecedence(op) < getPrecedence(operatorStack.peek()))
)
){
infix.add(operatorStack.pop());
}
//ow add the operator
operatorStack.push(op);
}
}
}
//if there are left over element sin stack then append them in the output
while(!operatorStack.isEmpty()){
infix.add(operatorStack.pop());
}
return infix;
}
private static int getPrecedence(String op){
if(op.equals("+") || op.equals("-")){
return 2;
}
if(op.equals("*") || op.equals("/")){
return 3;
}
if(op.equals("^")){
return 4;
}
return 0;
}
private static boolean isLeftAssociative(String op){
if(op.equals("+") || op.equals("-") || op.equals("*") || op.equals("/")){
return true;
}
if(op.equals("^")){
return false;
}
return false;
}
private static boolean isOperator(String op){
return op.matches("[-+*/^()]");
}
Evaluate RPN expression
Once we have generated reverse polish notation (RPN) of an expression then we can evaluate the expression using stack by the following simple procedure –
• While there are tokens to be read: • Read a token. • If its an operand then simply push to stack • If its an operator then replace the expression for this operator with the evaluated value. Pop second and first operand from stack and evaluate the expression for current operator. Then push the evaluated expression into stack. • At the end the stack top should be the evaluated value of the expression.
For example, for 342*15-/2*3/+ we the states of stack are : [] -> [3] -> [3,4] -> [3,4,2] -> [3,8] -> .. ->[3,8,1,5] -> [3,8,-4] -> [3,-2] -> [3,-2,2] -> [3,-4] -> [3,-4,3] -> [3,-1.33] -> [1.66]
Below is the O(n) implementation of the above algorithm which requires O(n) space.
public static double evaluateInfix(ArrayList<String> infix){
Stack<String> opStack = new Stack<String>();
for(String op : infix){
if(isOperator(op)){
//pop second operand frst (because it's in stack)
if(opStack.isEmpty()){
return Double.NaN;
}
String op2 = opStack.pop();
//pop first operand second (because it's in stack)
if(opStack.isEmpty()){
return Double.NaN;
}
String op1 = opStack.pop();
//evaluate the expression
double eval = evaluate(op1, op2, op);
if(eval == Double.NaN){
return Double.NaN;
}
//push the evaluated value to stack
opStack.push(eval+"");
}
else{
opStack.push(op);
}
}
if(opStack.size() != 1){
return Double.NaN;
}
return Double.parseDouble(opStack.pop());
}
private static double evaluate(String op1, String op2, String op){
if(op.equals("+")){
return Double.parseDouble(op1)+Double.parseDouble(op2);
}
else if(op.equals("-")){
return Double.parseDouble(op1)-Double.parseDouble(op2);
}
else if(op.equals("*")){
return Double.parseDouble(op1)*Double.parseDouble(op2);
}
else if(op.equals("/")){
double denm = Double.parseDouble(op2);
if(denm == 0){
return Double.NaN;
}
else {
return Double.parseDouble(op1)/Double.parseDouble(op2);
}
}
else return Double.NaN;
}