LintCode - Infix to Prefix / Convert Expression to Polish Notation

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

Example

For the expression [(5 − 6) * 7] (which represented by["(", "5", "−", "6", ")", "*", "7"]), the corresponding polish notation is [* - 5 6 7] (which the return value should be["*", "−", "5", "6", "7"]).

Polish notation, also known as Polish prefix notation or simply prefix notation
Its distinguishing feature is that it places operators to the left of their operands.
https://wxx5433.gitbooks.io/interview-preparation/content/part_ii_leetcode_lintcode/stack/convert_expression_to_polish_notation.html

Need some modification on Convert Expression to Reverse Polish Notation.

1. Need to scan the expression from right to left.
2. Each time ")" is met, put into opStack. (Instead of "(")
3. Each time "(" is met, pop from opStack until see ")". (The reason is that it evaluation from end to start)
4. Only pop op from element when priority(prevOp) > priority(op), instead of >=. The reason is the same, since we evaluate from end to start.

  public ArrayList<String> convertToPN(String[] expression) {
    ArrayList<String> result = new ArrayList<>();
    if (expression == null || expression.length == 0) {
      return result;
    }
    Stack<String> opStack = new Stack<>();
    for (int i = expression.length - 1; i >= 0; i--) {
      String token = expression[i];
      if (isNumber(token)) {
        result.add(token);
      } else if (token.equals("(")) {
        while (!opStack.peek().equals(")")) {
          result.add(opStack.pop());
        }
        opStack.pop();
      } else if (token.equals(")")) {
        opStack.push(token);
      } else {
        while (!opStack.isEmpty() && getPriority(opStack.peek()) > getPriority(token)) {
          result.add(opStack.pop());
        }
        opStack.push(token);
      }
    }
    while (!opStack.isEmpty()) {
      result.add(opStack.pop());
    }
    Collections.reverse(result);
    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;
    }
  }

1. public List<String> convertToPN(String[] expression) {  
2.     Stack<String> operand = new Stack<>();  
3.     Stack<String> operator = new Stack<>();  
4.     for(int i=expression.length-1; i>=0; i--) {  
5.         String s = expression[i];  
6.         if("+-*/".contains(s)) {  
7.             // note: must be >, not >=  
8.             while(!operator.isEmpty() && getPriority(operator.peek()) > getPriority(s)) {  
9.                 operand.push(operator.pop());  
10.             }  
11.             operator.push(s);  
12.         } else if(")".equals(s)) {  
13.             operator.push(s);  
14.         } else if("(".equals(s)) {  
15.             while(!operator.peek().equals(")")) {  
16.                 operand.push(operator.pop());  
17.             }  
18.             operator.pop();  
19.         } else {  
20.             operand.push(s);  
21.         }  
22.     }  
23.     while(!operator.isEmpty()) {  
24.         operand.push(operator.pop());  
25.     }  
26.     List<String> pn = new ArrayList<>(operand);  
27.     Collections.reverse(pn);  
28.     return pn;  
29. }  
30.   
31. private int getPriority(String s) {  
32.     char c = s.charAt(0);  
33.     if(c=='+' || c=='-') return 1;  
34.     if(c=='*' || c=='/') return 2;  
35.     return 0;  
36. }

http://www.jianshu.com/p/e21b83eef010

• 首先建立表达式树，如题[Expression Tree Build]
• Polish Notation即表达式树前序遍历的结果

https://simpledevcode.wordpress.com/2015/01/03/convert-infix-to-reverse-polish-notation-c-implementation/
Read full article from LintCode - Infix to Prefix / Convert Expression to Polish Notation - 我的博客 - ITeye技术网站