首先通过括号匹配的方法标记处多余的左右括号,在解析表达式的时候跳过标记部分。
输入中的负号都是以同一种形式,即’-‘左边存在左括号,通过这个辨别是输入负号还是减号。
若输入负号,则只需在负号前面加上一个0,就可以把其变成0-x这种形式,和输入只有正数是等价的。
当然,如果输入诸如-5这样的形势,加一个特判就好了,如果负数出现在等式中,则一定如上述所说的形式。
#include <iostream>
#include <cstring>
#include <stack>
#include <map>
using namespace std;
stack<int> num, stk;
stack<char> op;
string expp;
map<char, int> mp;
void calc() {
int x = num.top();num.pop();
int y = num.top(); num.pop();
char c = op.top(); op.pop();
int res = 1;
if (c == '+') res = x + y;
else if (c == '-') res = y - x;
else if (c == '*') res = x * y;
else if (c == '/') res = y / x;
else while(x--) res *= y;
num.push(res);
}
int main() {
cin >> expp;
int n = expp.size();
for (int i = 0; i < n; i++)
if (expp[i] == '(') stk.push(i);
else if (expp[i] == ')') {
if (!stk.size()) expp[i] = '#';
else stk.pop();
}
while (stk.size()) {
expp[stk.top()] = '#';
stk.pop();
}
mp['('] = 0;
mp['+'] = mp['-'] = 1;
mp['*'] = mp['/'] = 2;
mp['^'] = 3;
for (int i = 0; i < n; i++) {
char c = expp[i];
if (c != '#') {
if (c >= '0' && c <= '9') {
int x = c - '0', j;
for (j = i + 1; j < n && expp[j] <= '9' && expp[j] >= '0'; j++)
x = x * 10 + (expp[j] - '0');
num.push(x);
i = j - 1;
}
else if (c == '(') op.push(c);
else if (c == ')') {
while (op.top() != '(') calc();
op.pop();
} else {
if (c == '-' && expp[i - 1] == '(') {
num.push(0);
op.push(c);
continue;
}
while(op.size() && mp[op.top()] >= mp[c]) calc();
op.push(c);
}
}
}
while (op.size()) calc();
cout << num.top() << endl;
return 0;
}