【ACWing】151. 表达式计算4

题目地址：

https://www.acwing.com/problem/content/description/153/

给出一个表达式,其中运算符仅包含+,-,*,/,^（加 减 乘 整除 乘方）要求求出表达式的最终值。
数据可能会出现括号情况，还有可能出现多余括号情况。
数据保证不会出现大于或等于2 31 2^{31}231的答案。
数据可能会出现负数情况。
数据保证不会出现指数为负数的情况。
数据保证指数运算不会连续出现，例如2^2^3。

输入格式：
输入仅一行，即为表达式。

输出格式：
输出仅一行，既为表达式算出的结果。

可以用双栈的方法来做。这道题有很多需要注意的点：

1. 为了让栈里最后只剩下一个数，而不是出了循环还要继续做运算，我们可以用一对小括号把输入包起来；
2. 为了使得括号平衡，我们需要预处理一下，补齐缺失的括号；
3. 需要额外处理减号作为负号的情形。减号应该被当成负号，当且仅当，其之前的字符不是数字也不是左括号；如果负号之后是左括号，我们需要将-(变成-1*(，这样好处理，即符号栈加入*，数字栈加入-1；如果负号之后是数字，我们直接将数字截取出来即可。

代码如下：

#include<iostream>#include<stack>usingnamespacestd;usingll=longlong;string s;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);cin>>s;s='('+s+')';intl=0,r=0;for(charch:s){if(ch=='(')l++;elseif(ch==')')r++;}if(l>r)s=s+string(l-r,')');if(l<r)s=string(r-l,'(')+s;autof=[](charop){switch(op){case'(':return0;case'+':case'-':return1;case'*':case'/':return2;case'^':return3;default:return-1;}};stack<ll>stk;stack<char>ops;autocalc=[](auto&stk,auto&ops){charop=ops.top();ops.pop();if(op=='('||op==')')return;ll y=stk.top();stk.pop();ll x=stk.top();stk.pop();if(op=='+')stk.push(x+y);elseif(op=='-')stk.push(x-y);elseif(op=='*')stk.push(x*y);elseif(op=='/')stk.push(x/y);else{if(!x)stk.push(0);else{ll res=1;while(y){if(y&1)res*=x;y>>=1;x*=x;}stk.push(res);}}};for(inti=0;i<s.size();i++){charch=s[i];if(isdigit(ch)){intj=i;ll x=0;while(isdigit(s[j]))x=x*10+s[j++]-'0';i=j-1;stk.push(x);}elseif(ch=='(')ops.push('(');elseif(ch==')'){while(ops.top()!='(')calc(stk,ops);ops.pop();}elseif(ch=='-'&&i&&!isdigit(s[i-1])&&s[i-1]!=')'){if(s[i+1]=='('){stk.push(-1);ops.push('*');}else{intj=i+1;ll x=0;while(isdigit(s[j]))x=x*10+s[j++]-'0';stk.push(-x);i=j-1;}}else{while(f(ops.top())>=f(ch))calc(stk,ops);ops.push(ch);}}printf("%lld\n",stk.top());}

时空复杂度O ( n ) O(n)O(n)，n nn为输入长度。