实现一个基本的计算器来计算一个简单的字符串表达式。
字符串表达式可以包含左括号 ( ，右括号)，加号+ ，减号 -，非负整数和空格 。
假定所给的表达式语句总是正确有效的。
例如：
"1 + 1" = 2
" 2-1 + 2 " = 3
"(1+(4+5+2)-3)+(6+8)" = 23
注意：不要使用内置的库函数 eval。
详见：https://leetcode.com/problems/basic-calculator/description/
Java实现：
1.遇到数字位，看后一位是否为数字，若是位数字，当前位需要进十.
2.开始设sign = 1，若遇到 ' - ', sign 改为 -1，若遇到 '+'，sign改回1.
3.遇到 '(', 压栈，先压之前的res，后压sign，然后初始化res和sign.
4.遇到')' ,出栈，当前res先乘pop() 出来的 sign，再加上pop()出来的之前结果.
class Solution {
public int calculate(String s) {
if(s == null || s.length() == 0){
return -1;
}
int res = 0;
int sign = 1;
Stack<Integer> stk = new Stack<Integer>();
for(int i = 0; i<s.length(); i++){
char c = s.charAt(i);
if(Character.isDigit(c)){
int cur = c-'0';
while(i+1 < s.length() && Character.isDigit(s.charAt(i+1))){
cur = cur*10 + s.charAt(i+1) - '0';
++i;
}
res += sign*cur;
}else if(c == '-'){
sign = -1;
}else if(c == '+'){
sign = 1;
}else if(c == '('){
stk.push(res);
res = 0;
stk.push(sign);
sign = 1;
}else if(c == ')'){
res = res*stk.pop() + stk.pop();
}
}
return res;
}
}
参考：https://www.cnblogs.com/Dylan-Java-NYC/p/4825019.html
C++实现：
class Solution {
public:
int calculate(string s) {
int size=s.size();
if(size==0||s.empty())
{
return 0;
}
int res=0,sign=1;
stack<int> stk;
for(int i=0;i<size;++i)
{
char c=s[i];
if(c>='0')
{
int num=0;
while(i<size&&s[i]>='0')
{
num=num*10+s[i++]-'0';
}
res+=sign*num;
--i;
}
else if(c=='+')
{
sign=1;
}
else if(c=='-')
{
sign=-1;
}
else if(c=='(')
{
stk.push(res);
stk.push(sign);
res=0;
sign=1;
}
else if(c==')')
{
res*=stk.top();
stk.pop();
res+=stk.top();
stk.pop();
}
}
return res;
}
};
参考：http://www.cnblogs.com/grandyang/p/4570699.html