[LeetCode] Basic Calculator

Problem:

Implement a basic calculator to evaluate a simple expression string.
The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces .
You may assume that the given expression is always valid.
Some examples:
"1 + 1" = 2
" 2-1 + 2 " = 3
"(1+(4+5+2)-3)+(6+8)" = 23

思路：

输入的表达式可以被看作 infix notation，为了对括号进行处理，要先将 infix notation 转换成 postfix notation (也就是 Reverse Polish Notation)，然后再计算 postfix notation 的值即可，计算的方法就是LeetCode上的那道“Evaluate Reverse Polish Notation”。

注：将 infix notation 转换为  postfix notation 的算法：

http://cs.nyu.edu/courses/Fall12/CSCI-GA.1133-002/notes/InfixToPostfixExamples.pdf

-------------------------------------------------------------------

The input expression could be seen as an infix notation. To take the parentheses away, I choose to convert the infix notation to postfix notation (aka. Reverse Polish Notation). Then, calculate the value of the postfix notation, which has already been covered by the "Evaluate Reverse Polish Notation" problem on LeetCode.

The algorithm to convert infix notation to postfix notation:
http://cs.nyu.edu/courses/Fall12/CSCI-GA.1133-002/notes/InfixToPostfixExamples.pdf

Java Code:

public class Solution {
    public static int calculate(String s) {
        String ss = toRPN(s);
        String tokens[] = toRPN(s).split("\\s+");
        int returnValue = 0;
        
        String operators = "+-";
 
        Stack<String> stack = new Stack<String>();
 
        for(String t : tokens){
            if(!operators.contains(t)){
                stack.push(t);
            }else{
                int a = Integer.valueOf(stack.pop());
                int b = Integer.valueOf(stack.pop());
                int index = operators.indexOf(t);
                switch(index){
                    case 0:
                        stack.push(String.valueOf(a+b));
                        break;
                    case 1:
                        stack.push(String.valueOf(b-a));
                        break;
                }
            }
        }
 
        returnValue = Integer.valueOf(stack.pop());
 
        return returnValue;
    }
    
    public static String toRPN(String input) {
        char[] in = input.toCharArray();
        Stack<Character> stack = new Stack<Character>();
        StringBuilder out = new StringBuilder();

        for (int i = 0; i < in.length; i++)
            switch (in[i]) {
            case '+':
            case '-':
                while (!stack.empty() && stack.peek() != '(') {
                    out.append(' ');
                    out.append(stack.pop());
                }
                out.append(' ');
                stack.push(in[i]);
                break;
            case '(':
                stack.push(in[i]);
                break;
            case ')':
                while (!stack.empty() && stack.peek() != '(') {
                    out.append(' ');
                    out.append(stack.pop());
                }
                stack.pop();
                break;
            case ' ':
                break;
            default:
                out.append(in[i]);
                break;
            }

        while (!stack.isEmpty()) {
            out.append(' ');
            out.append(stack.pop());
            
        }
        return out.toString();
    }
}