实现一个基本的计算器来计算一个简单的字符串表达式 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 表示一个有效的表达式
通过次数42,872提交次数104,896
| class Solution { public: stack<long>n ; //存储数字 stack<char>t; //储存符号 int calculate(string s) { int m = s.length(); long tag = -1; n.push(0); for(int i = 0;i<m;i++){ if(s[i]==' '){ //当遇到空格的情况下 continue; } if(s[i]>='0'&&s[i]<='9'){ //当遇到数字的情况下 注意数字并不一定是个位的 需要累加和并且入栈 if(tag == -1){ tag = s[i]-'0'; }else{ tag = tag * 10 +s[i]-'0'; } } else{ if(tag!=-1){ //是否为数字 并将数字入栈 n.push(tag); tag = -1; } if(s[i]=='+'||s[i]=='-'){ //处理符号情况 while(!t.empty()){ if(t.top()=='('){ break; } long num1 = n.top(); //s每次弹出两个数字 t 弹出一个符号 n.pop(); long num2 = n.top(); n.pop(); if(t.top()=='+'){ //将运算的结果入栈 n.push(num1+num2); t.pop(); }else{ n.push(num2-num1); t.pop(); } } t.push(s[i]); //当前符号入栈 } else if(s[i]=='('||s[i]==')') { //遇见（ ） 情况 if(s[i]=='('){ t.push(s[i]); } if(s[i]==')'){ while(t.top()!='('){ //不断的进行运算 long num1 = n.top(); //s每次弹出两个数字 t 弹出一个符号 n.pop(); long num2 = n.top(); n.pop(); if(t.top()=='+'){ //将运算的结果入栈 n.push(num1+num2); t.pop(); } else{ n.push(num2-num1); t.pop(); } } t.pop(); //弹出 ( } } } } if(tag!=-1){ n.push(tag); } while(!t.empty()){ long num1 = n.top(); //s每次弹出两个数字 t 弹出一个符号 n.pop(); long num2 = n.top(); n.pop(); if(t.top()=='+'){ //将运算的结果入栈 n.push(num1+num2); t.pop(); }else{ n.push(num2-num1); t.pop(); } } return n.top(); } }; |