难度 hard
给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。

示例 1：

输入：s = "1 + 1"
输出：2
示例 2：

输入：s = " 2-1 + 2 "
输出：3
示例 3：

输入：s = "(1+(4+5+2)-3)+(6+8)"
输出：23

提示：

1 <= s.length <= 3 * 105
s 由数字、'+'、'-'、'('、')'、和 ' ' 组成
s 表示一个有效的表达式

解题思路：这道题目限制了输入字符中只有数字、加减符号和括号，没有乘除，因此难度还好，这里还是用栈来解决，我们用一个int型变量sign表示运算符，初始化为1，遍历字符串，如果遇到数字符号，则转换为数字，当遇到符号的时候，开始进行结果运算，那当前算出来的数字乘以符号位，加到结果res中，下面就是根据符号位的不同来进行不同操作，如果是'+'，那sign赋值为1，如果是'-'则赋值为-1，如果是左括号，那把res和sign同时入栈，res是符号位之前的运算结果，符号位是当前这个括号内算出来的结果的符号表示，同时把res置零，sign置一，这是一开始的初值，因为左括号和右括号之间本质上也是一个完整的字符串，我们这个函数本来也是计算这个的，因此这里有点像递归调用。当遇到右括号的时候，我们已经计算了中间这一部分的结果，这个结果乘以栈顶的符号位，再加上栈顶的前一部分的结果，就是累加至今的结果。

代码 t75 s50

class Solution {
    public int calculate(String s) {
        Stack<Integer> st = new Stack<>();
        int n = s.length(), res = 0, sign = 1;
        for(int i=0; i<n; i++){
            if(s.charAt(i)>='0'){
                int num = 0;
                while(i<n && s.charAt(i)>='0') num = num * 10 + (s.charAt(i++) - '0');
                res += sign * num;
                i--;
            }else if(s.charAt(i)=='+') sign = 1;
            else if(s.charAt(i)=='-') sign = -1;
            else if(s.charAt(i)=='('){
                st.push(res);
                st.push(sign);
                res = 0;
                sign = 1;
            }else if(s.charAt(i)==')'){
                res *= st.peek();
                st.pop();
                res += st.peek();
                st.pop();
            }
        }
        return res;
    }
}

参考资料：
http://www.cnblogs.com/grandyang/p/4570699.html