AcWing 151. 表达式计算4
原题链接
中等
作者:
zxmcoder
,
2021-03-11 22:31:45
,
所有人可见
,
阅读 400
#include <iostream>
#include <cctype>
#include <stack>
#include <string>
#include <unordered_map>
#include <cmath>
using namespace std;
unordered_map<char, int> pr;
stack<int> num;
stack<char> op;
void eval() {
int b = num.top(); num.pop();
int a = num.top(); num.pop();
char c = op.top(); op.pop();
int r;
if(c == '+') r = a + b;
if(c == '-') r = a - b;
if(c == '*') r = a * b;
if(c == '/') r = a / b;
if(c == '^') r = pow(a, b);
num.push(r);
}
int main() {
string str;
cin >> str;
pr['('] = 0;
pr['+'] = pr['-'] = 1;
pr['*'] = pr['/'] = 2;
pr['^'] = 3;
pr[')'] = 4;
string left;
for(int i = 0; i <= str.size(); ++i) left += '(';
str = left + str + ')';
// cout << str << endl;
for(int i = 0; i < str.size(); ++i) {
char c = str[i];
if(isdigit(c)) {
int j = i, x = 0;
while(j < str.size() && isdigit(str[j])) x = 10 * x + (str[j ++] - '0');
i = j - 1;
num.push(x);
}
else if(c == '(') op.push(c);
else if(c == ')') {
while(op.size() && op.top() != '(') eval();
op.pop();
}
else {
if(c == '-') {
if((i == 0) || (i && !(str[i - 1] >='0' && str[i - 1] <= '9' || str[i - 1] == ')'))){
// int j = i + 1, x = 0;
// while(j < str.size() && isdigit(str[j])) x = 10 * x + (str[j ++] - '0');
// i = j - 1;
// num.push(-x);
// continue;
num.push(0);
}
}
while(op.size() && pr[op.top()] >= pr[c]) eval();
op.push(c);
}
}
while(op.size() && op.top() != '(') eval();
cout << num.top() << endl;
}