1.“-”可能是减号或者负号,若是负号,在前面补0即可
2.括号数量可能不一样多,可以补齐使左右括号数量相等
3.以上两步完成后,符合基础课模板题3302. 表达式求值 的条件,直接背模板即可(注,本题多了个运算符乘方,只需在哈希表中添加一个乘方即可)
#include <iostream>
#include <stack>
#include <unordered_map>
using namespace std;
stack<char> op;
stack<int> num;
int qmi(int a, int k) //快速幂
{
int res = 1;
while(k)
{
if(k & 1) res = res * a;
a = a * a;
k >>= 1;
}
return res;
}
void eval()
{
int b = num.top(); num.pop();
int a = num.top(); num.pop();
char c = op.top(); op.pop();
int x;
if(c == '+') x = a + b;
else if(c == '-') x = a - b;
else if(c == '*') x = a * b;
else if(c == '/') x = a / b;
else if(c == '^') x = qmi(a, b);
num.push(x);
}
int main()
{
string s;
cin >> s;
unordered_map<char, int> pr{{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}, {'^', 3}};
//l, r分别为输入串中左右括号数量
int l = 0, r = 0;
for(int i = 0; i < s.size(); i ++ )
if(s[i] == '(') l ++ ;
else if(s[i] == ')') r ++ ;
char c;
if(l > r) c = ')'; // 右括号少,补右括号
else if(l < r) c = '('; // 左括号少,补左括号
string add;
for(int i = 0; i < abs(l - r); i ++ ) add += c;
// 使表达式中左右括号数量相等,以便直接套模板
if(l > r) s = s + add;
else if(l < r) s = add + s;
// 处理-为负号的情况,在前面补0即可
for(int i = 0; i < s.size(); i ++ )
{
if(s[i] == '-' && i == 0) s = '0' + s;
else if(s[i] == '-' && i > 0 && !isdigit(s[i - 1]) && s[i - 1] != ')')
{
s.insert(i - 1, "0");
i ++ ;
}
}
// 基础课模板
for(int i = 0; i < s.size(); i ++ )
{
if(isdigit(s[i]))
{
int j = i, x = 0;
while(j < s.size() && isdigit(s[j]))
x = x * 10 + s[j ++ ] - '0';
num.push(x);
i = j - 1;
}
else if(s[i] == '(') op.push(s[i]);
else if(s[i] == ')')
{
while(op.top() != '(') eval();
op.pop();
}
else
{
while(op.size() && op.top() != '(' && pr[op.top()] >= pr[s[i]])
eval();
op.push(s[i]);
}
}
while(op.size()) eval();
cout << num.top() << endl;
return 0;
}