Massive Algorithms: LintCode - Infix to Postfix / Convert Expression to Reverse Polish Notation

LintCode - Infix to Postfix / Convert Expression to Reverse Polish Notation

LintCode - Infix to Postfix / Convert Expression to Reverse Polish Notation - 我的博客 - ITeye技术网站
Given an expression string array, return the Reverse Polish notation of this expression. (remove the parentheses)
Aka, convert infix notation to postfix notation.

Example

For the expression [3 - 4 + 5] (which denote by ["3", "-", "4", "+", "5"]), return[3 4 - 5 +] (which denote by ["3", "4", "-", "5", "+"])

Reverse Polish notation (RPN) is a mathematical notation in which every operator follows all of its operands, in contrast to Polish notation, which puts the operator in the prefix position. It is also known as postfix notation and is parenthesis-free as long as operator arities are fixed.

The infix expression "5 + ((1 + 2) × 4) − 3" can be written down like this in RPN:
5 1 2 + 4 × + 3 −
https://wxx5433.gitbooks.io/interview-preparation/content/part_ii_leetcode_lintcode/stack/convert_expression_to_reverse_polish_notation.html

  public ArrayList<String> convertToRPN(String[] expression) {
    ArrayList<String> result = new ArrayList<>();
    if (expression == null || expression.length == 0) {
      return result;
    }
    Stack<String> opStack = new Stack<>();
    for (String token : expression) {
      if (isNumber(token)) {
        result.add(token);
      } else if (token.equals("(")) {
        opStack.push(token);
      } else if (token.equals(")")) {
        while (!opStack.peek().equals("(")) {
          result.add(opStack.pop());
        }
        opStack.pop();
      } else {
        while (!opStack.isEmpty() && getPriority(opStack.peek()) >= getPriority(token)) {
          result.add(opStack.pop());
        }
        opStack.push(token);
      }
    }
    while (!opStack.isEmpty()) {
      result.add(opStack.pop());
    }
    return result;
  }

  private boolean isNumber(String token) {
    return Character.isDigit(token.charAt(0));
  }

  private int getPriority(String op) {
    if (op.equals("(")) {
      return 0;
    } else if (op.equals("+") || op.equals("-")) {
      return 1;
    } else {
      return 2;
    }
  }

https://xmruibi.gitbooks.io/interview-preparation-notes/content/Algorithm/Expression/ConvertExpressionToRPN.html

Always consider stack firstly, when meet a reverse polish notation problem.
The operator priority (*, /) > (+, -), when get the operator is less priority than stack top element, pop the stack util the element has the same priority as the current operator and output the pop element in result list.
Push the "(" always but pop the stack when get the ")" until stack has pop the corresponding "(".
When get the operand, just output in result list.

  public ArrayList<String> convertToRPN(String[] expression) {
    ArrayList<String> result = new ArrayList<>();
    if (expression == null || expression.length == 0) {
      return result;
    }
    Stack<String> opStack = new Stack<>();
    for (String token : expression) {
      if (isNumber(token)) {
        result.add(token);
      } else if (token.equals("(")) {
        opStack.push(token);
      } else if (token.equals(")")) {
        while (!opStack.peek().equals("(")) {
          result.add(opStack.pop());
        }
        opStack.pop();
      } else {
        while (!opStack.isEmpty() && getPriority(opStack.peek()) >= getPriority(token)) {
          result.add(opStack.pop());
        }
        opStack.push(token);
      }
    }
    while (!opStack.isEmpty()) {
      result.add(opStack.pop());
    }
    return result;
  }

  private boolean isNumber(String token) {
    return Character.isDigit(token.charAt(0));
  }

  private int getPriority(String op) {
    if (op.equals("(")) {
      return 0;
    } else if (op.equals("+") || op.equals("-")) {
      return 1;
    } else {
      return 2;
    }
  }

http://hehejun.blogspot.com/2014/12/algorithmconvert-expression-to-reverse.html
括号只是决定运算的优先顺序，所以不会出现在我们最后的逆波兰式当中。根据以上两个要点，先写出转换成逆波兰式的算法，之后再来分别解释，首先维护两个栈，第一个栈只存操作符，第二个栈是存逆波兰式的结果，第一个栈中我们先压入'#'并认为它的优先级最低（这一步可以让我们避免check栈空的情况）

public List<String> convertToRPN(String[] expression) {
List<String> rpn = new ArrayList<>();
Stack<String> opstack = new Stack<>();
for(String op:expression) {
if("+-*/".contains(op)) {
while(!opstack.isEmpty() && getPriority(opstack.peek()) >= getPriority(op)) {
rpn.add(opstack.pop());
}
opstack.push(op);
} else if("(".equals(op)) {
opstack.push(op);
} else if(")".equals(op)) {
while(!"(".equals(opstack.peek())) {
rpn.add(opstack.pop());
}
opstack.pop();
}
else {
rpn.add(op);
}
}
while(!opstack.isEmpty()) {
rpn.add(opstack.pop());
}
return rpn;
}
private int getPriority(String s) {
char c = s.charAt(0);
if(c == '+' || c== '-') {
return 1;
} else if(c == '*' || c == '/') {
return 2;
}
return 0;
}

public String convertToReversePolish(String exp) {
if (exp == null)
return null;
String res = "";
int len = exp.length();
Stack<Character> operator = new Stack<Character>();
Stack<String> reversePolish = new Stack<String>();
//avoid checking empty
operator.push('#');
for (int i = 0; i < len;) {
//deal with space
while (i < len && exp.charAt(i) == ' ')
i++;
if (i == len)
break;
//if is number
if (isNum(exp.charAt(i))) {
String num = "";
while (i < len && isNum(exp.charAt(i)))
num += exp.charAt(i++);
reversePolish.push(num);
//is operator
} else if (isOperator(exp.charAt(i))) {
char op = exp.charAt(i);
switch (op) {
case '(':
operator.push(op);
break;
case ')':
while (operator.peek() != '(')
reversePolish.push(Character.toString(operator.pop()));
operator.pop();
break;
case '+':
case '-':
if (operator.peek() == '(')
operator.push(op);
else {
while (operator.peek() != '#' && operator.peek() != '(')
reversePolish.push(Character.toString(operator.pop()));
operator.push(op);
}
break;
case '*':
case '/':
if (operator.peek() == '(')
operator.push(op);
else {
while (operator.peek() != '#' && operator.peek() != '+' &&
operator.peek() != '-' && operator.peek() != '(')
reversePolish.push(Character.toString(operator.pop()));
operator.push(op);
}
break;
}
i++;
}
}
while (operator.peek() != '#')
reversePolish.push(Character.toString(operator.pop()));
while (!reversePolish.isEmpty())
res = res.length() == 0? reversePolish.pop() + res: reversePolish.pop() + " " + res;
return res;
}

public boolean isOperator(char c) {
return c == '+' || c == '-' || c == '*' || c == '/' || c == '(' || c == ')';
}

public boolean isNum(char c) {
return c - '0' >= 0 && c - '0' <= 9;
}
Converting infix to RPN (shunting-yard algorithm) « andreINC
Posted on If you’ve tried to write your own calculator (something in the style of gcalctool ) you’ve probably had to build a simple converter for your mathematical expressions from infix notation to RPN (Reverse Polish Notation). Inspired by this classical SPOJ challenge I wanted to write my own simplified version of an expression converter. If this topic is new for you, or you need to refresh your memory please don’t skip the following paragraph.
http://andreinc.net/2010/10/05/converting-infix-to-rpn-shunting-yard-algorithm/

A simplified version of the Shunting-yard algorithm (complete version)
For all the input tokens [S1]: Read the next token [S2]; If token is an operator (x) [S3]: While there is an operator (y) at the top of the operators stack and either (x) is left-associative and its precedence is less or equal to that of (y), or (x) is right-associative and its precedence is less (No equal) than (y) [S4]: Pop (y) from the stack [S5]; Add (y) output buffer [S6]; Push (x) on the stack [S7]; Else If token is left parenthesis, then push it on the stack [S8]; Else If token is a right parenthesis [S9]: Until the top token (from the stack) is left parenthesis, pop from the stack to the output buffer [S10]; Also pop the left parenthesis but don’t include it in the output buffer [S11]; Else add token to output buffer [S12]. While there are still operator tokens in the stack, pop them to output [S13] Note: [SN] Relate with code.

        // Associativity constants for operators: encapsulate in an Operator class.
 private static final int LEFT_ASSOC = 0;
 private static final int RIGHT_ASSOC = 1;

 // Supported operators
 private static final Map<String, int[]> OPERATORS = new HashMap<String, int[]>();
 static {
  // Map<"token", []{precendence, associativity}>
  OPERATORS.put("+", new int[] { 0, LEFT_ASSOC });
  OPERATORS.put("-", new int[] { 0, LEFT_ASSOC });
  OPERATORS.put("*", new int[] { 5, LEFT_ASSOC });
  OPERATORS.put("/", new int[] { 5, LEFT_ASSOC });
  OPERATORS.put("%", new int[] { 5, LEFT_ASSOC });
  OPERATORS.put("^", new int[] { 10, RIGHT_ASSOC });
 }

 public static String[] infixToRPN(String[] inputTokens) { // simplify condition: use string array
  ArrayList<String> out = new ArrayList<String>();
  Stack<String> stack = new Stack<String>();
  // For all the input tokens [S1] read the next token [S2]
  for (String token : inputTokens) {
   if (isOperator(token)) {
    // If token is an operator (x) [S3]
    while (!stack.empty() &amp;&amp; isOperator(stack.peek())) {
     // [S4]
     if ((isAssociative(token, LEFT_ASSOC) &amp;&amp; cmpPrecedence(
       token, stack.peek()) <= 0)
       || (isAssociative(token, RIGHT_ASSOC) &amp;&amp; cmpPrecedence(
         token, stack.peek()) < 0)) {
      out.add(stack.pop());  // [S5] [S6]
      continue;
     }
     break;
    }
    // Push the new operator on the stack [S7]
    stack.push(token);
   } else if (token.equals("(")) {
    stack.push(token);  // [S8]
   } else if (token.equals(")")) {
    // [S9]
    while (!stack.empty() &amp;&amp; !stack.peek().equals("(")) {
     out.add(stack.pop()); // [S10]
    }
    stack.pop(); // [S11]
   } else {
    out.add(token); // [S12]
   }
  }
  while (!stack.empty()) {
   out.add(stack.pop()); // [S13]
  }
  String[] output = new String[out.size()];
  return out.toArray(output);
 }

When n is a negative integer and b is not zero, bⁿ is naturally defined as 1/b⁻ⁿ, preserving the property bⁿ × b^m = b^n + m.

Right-associative operations include the following:

Exponentiation of real numbers:

x^{y^z}=x^{(y^z)}.\,

The reason exponentiation is right-associative is that a repeated left-associative exponentiation operation would be less useful. Multiple appearances could (and would) be rewritten with multiplication:

(x^y)^z=x^{(yz)}.\,

http://www.zrzahid.com/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 usingShunting-yard algorithm developed by Dijkstra. This is a O(n) time and O(n) space 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.

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("(");
   }
   //otherwise if it is a right parenthesis then pop the stack until 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;
}

http://en.wikipedia.org/wiki/Shunting-yard_algorithm#The_algorithm_in_detail
Also read http://www.geeksforgeeks.org/expression-evaluation/
Read full article from LintCode - Infix to Postfix / Convert Expression to Reverse Polish Notation - 我的博客 - ITeye技术网站

LintCode - Infix to Postfix / Convert Expression to Reverse Polish Notation

Labels

Popular Posts