1. 问题描述
计算字符串表达式的值，表达式中只含有(,),+,-,空格和非负整数。例如： “1 + 1” = 2 ” 2-1 + 2 ” = 3 “(1+(4+5+2)-3)+(6+8)” = 23 原文链接：https://leetcode.com/problems/basic-calculator/
2. 方法与思路2.1 利用后缀表达式计算
一种思路是按照常规的方法，由中缀表达式转到后缀表达式在进行计算。转换过程如下： 依次遍历字符串，做一下操作。
class Solution {public:int GetNum(string poststr,int *i){int tmp =0;while(poststr[(*i)] >= ‘0’ && poststr[(*i)] <= ‘9’){tmp = tmp*10 + ( poststr[(*i)] – ‘0’);(*i) ++;}return tmp;}int postcal(string poststr){stack<int> s;int i,a,b,tmp =0;for(i=0; i < poststr.length(); i++){switch(poststr[i]){case ‘ ‘:continue;case ‘+’:b = s.top(); s.pop();a = s.top(); s.pop();s.push(a+b);break;case ‘-‘:b = s.top(); s.pop();a = s.top(); s.pop();s.push(a-b);break;default:s.push(GetNum(poststr,&i));}}return s.top();}int calculate(string s) {int re =0,tmp = 0;stack<char> num;string poststr=””;for(int i=0; i < s.length(); i++){switch(s[i]){case ‘(‘:num.push(s[i]);break;case ‘ ‘:continue;case ‘)’:poststr += ” “;while(num.top() != ‘(‘){poststr += num.top();num.pop();}num.pop();break;case ‘+’:case ‘-‘:poststr += ” “;while(!num.empty() && num.top() != ‘(‘){poststr +=num.top();num.pop();}num.push(s[i]);break;default:poststr += s[i];}}poststr += ” “;while(!num.empty()){poststr += num.top();num.pop();}//cout<<poststr<<endl;return postcal(poststr);}};
但是这种方法却超时了，头晕。还得好好地再看看，，有没有可优化的地方！！！
2.2 表达式化简
由于表达式中只含有括号和加减法运算，我们可以通过加减法的规律对表达式进行化简，然后求值。
class Solution {public:int calculate(string s) {stack<int> num;num.push(1);char op = ‘+’;long re = 0;for (int i=0; i<s.length(); i++) {switch(s[i]) {case ‘ ‘:break;case ‘+’:case ‘-‘:op = s[i];break;case ‘(‘:num.push(num.top() * (op == ‘-‘ ? -1 : 1));op = ‘+’;break;case ‘)’:num.pop();break;default:int tmp = 0;while ( s[i] >= ‘0’ && s[i] <= ‘9’) {tmp = tmp * 10 + s[i] – ‘0’;i++;}i–;re += (op == ‘-‘?-1:1)*num.top()*tmp;}}return re;}};
快乐要有悲伤作陪，雨过应该就有天晴。
