Basic Calculator

Q:
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

A:
下面的是递归的思路。但是，这样写是不行的。
自己考虑下，有哪两个错误。 (答案在最后一行)

public class Solution {
    public int calculate(String s) {
        s = s.trim();
        if(s.length()==0)
            return 0;
        // detach parentheses  ( )
        int i = s.indexOf('(');
        if(i>=0){
            int j = s.lastIndexOf(')');
            s = s.substring(0,i)+ calculate(s.substring(i+1, j))+s.substring(j+1);
        }
        int end = 0; // always start from 0
        while(end<s.length() && Character.isDigit(s.charAt(end)) ){
            end++;
        }
        int a = Integer.parseInt(s.substring(0,end));
        s = s.substring(end).trim();
        if(s.length()==0 )
            return a;
        if(s.charAt(0)=='+')
            return a+calculate(s.substring(1));
        else
            return a - calculate(s.substring(1));
    }
}
 

还是需要用Stack

下面的解法是用的2个Stack的思路 ------

public class Solution { 
    public int calculate(String s) {
        Stack<Integer> numStack = new Stack();
        numStack.push(0); // in case that s is empty
        Stack<Character> opStack = new Stack();
        for(int i =0;i<s.length();i++){
            int end = i;
            while(end<s.length() && (Character.isDigit(s.charAt(end)) || s.charAt(end)==' ')){
                end++;
            }
            String str = s.substring(i,end).trim();
            if(str.length()>0){ // just find a number
                int val = Integer.parseInt(str);
                numStack.push(val);
                check(numStack,opStack);
            }
            if(end<s.length()){
                char ch = s.charAt(end);
                opStack.push(ch);
                if(ch == ')')
                    check(numStack,opStack);
            }
            i = end;
        }
        return numStack.pop();
    }
    private void check(Stack<Integer> numStack,Stack<Character> opStack ){
        if(opStack.isEmpty())
            return;
        if(opStack.peek() ==')'){
            opStack.pop();// first on opStack is ')'
            opStack.pop();// first on opStack is '('
            check(numStack,opStack );
            return;
        }
        // just added a number
        if( opStack.peek()!='(') {
            int b = numStack.pop(), a = numStack.pop();
            char ch = opStack.pop();
            if (ch == '+')
                numStack.push(a + b);
            else
                numStack.push(a - b);
        }
    }
}

 

**************错误就是出在每次都要substring上。  下面是更改的代码***************

别人的代码

public class Solution {
    public int calculate(String s) {
        Stack<Integer> stack = new Stack<>();
        stack.push(1);
        stack.push(1);
        int res = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (Character.isDigit(c)) {
                int num = c - '0';
                int j = i + 1;
                while (j < s.length() && Character.isDigit(s.charAt(j))) {
                    num = 10 * num + (s.charAt(j) - '0');
                    j++;
                }
                res += stack.pop() * num;
                i = j - 1;
            } else if (c == '+' || c == '(') {
                stack.push(stack.peek());
            } else if (c == '-') {
                stack.push(-1 * stack.peek());
            } else if (c == ')') {
                stack.pop();
            }
        }
        return res;
    }
}

Mistakes:
1：  自己的解法有个最需要注意的问题就是：   pop完了（）两个运算符之后，要再 调用check（），因为我们相当于重新加入了一个运算数了



————————————————————————————————————
第一个解法，会造成某个数字是负数。再代入的话，就破坏原题目的简洁了
另外，  可能有多个括号并列的情况存在。