acwing 151. 表达式计算4(栈)

题目链接

题目大意

  略

解题思路

  用两个栈来处理，一个栈处理操作数，一个栈处理数字，如果当前的操作数的优先级不大于栈顶的优先级的话，那么前面的就可以先算出来。
  一些细节:
  1.因为题目中可能会有右括号比左括号多的情况，所以先在左边加上和字符串等长的左括号。
  2.为了让最后所有的数字变成一个数，在左右各加一个括号。
  2.遇到负号而不是减号的情况。如果是负号的话，其左边必定是左括号(即便它是第一个字符也同样，因为我们在左边加的有左括号)，我们可以把它变成-1和'*'，这样就不用考虑后面跟的是数字还是括号了。

代码

#include<bits/stdc++.h>
#define zjlnb 0
#define endl '
'
#define x first
#define y second
#define clr(arr,a) memset(arr, a, sizeof(arr))
#define IOS ios::sync_with_stdio(false)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
typedef pair<ll, int> Pll;
const double pi = acos(-1.0);
const double eps = 1e-10;
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;
const int maxn = 2e5+10;
stack<char> op;
stack<int> num;
int mp[1000];
void calc() {
    int b = num.top(); num.pop();
    int f = num.top(); num.pop();
    char c = op.top(); op.pop();
    if (c=='+') f += b;
    else if (c=='-') f -= b;
    else if (c=='*') f *= b;
    else if (c=='/') f /= b;
    else if (c=='^') f = pow(f, b)+1e-13; 
    num.push(f);
}
int main(void) {
    mp['+'] = mp['-'] = 1, mp['*'] = mp['/'] = 2, mp['^'] = 3; 
    string s, t; cin >> s;
    for (int i = 0; i<s.size(); ++i) t += '('; //防止'('比')'少
    s = '('+t+s+')'; //多加一对"()"，方便最后把所有数字处理成一个数字
    int sz = s.size();
    for (int i = 0; i<sz; ++i) {
        if (isdigit(s[i])) { //处理数字
            int res = s[i]-'0';
            while(i+1<sz && isdigit(s[i+1])) {
                ++i;
                res = res*10+s[i]-'0';
            }
            num.push(res);
        }
        else {
            if (s[i]=='-' && i && s[i-1]=='(' && i+1<sz) { 
                //负号直接处理成乘以-1的形式，既可以满足括号前面加负号的情况，也能满足数字本身是负数的情况
                num.push(-1);
                op.push('*');
            }
            else if (mp[s[i]]) {
                while(!op.empty() && mp[op.top()]>=mp[s[i]]) calc();
                //如果前面的操作数的优先级不小于当前的操作数的优先级，就把前面的都处理了，注意'('要留着
                //这里'('的优先级被我设成了0，所以就不用再判'('了
                op.push(s[i]);
            }
            else {
                if (s[i]=='(') op.push(s[i]);
                else if (s[i]==')') {
                    while(!op.empty() && op.top()!='(') calc();
                    op.pop(); //遇到')'处理到遇到'('为止，并且要把'('弹出
                    //cout << num.top() << endl;
                }
            }
        }
    }
    cout << num.top() << endl;
    return zjlnb;
}