题目描述
给出一个表达式,其中运算符仅包含+,-,*,/,^
(加 减 乘 整除 乘方)要求求出表达式的最终值。
数据可能会出现括号情况,还有可能出现多余括号情况。
数据保证不会出现大于或等于231的答案。
数据可能会出现负数情况。
样例
输入样例:
(2+2)^(1+1)
输出样例:
16
算法1
(模拟) $O(n)$
通过模拟的方法求解。
1.对字符串进行预先处理,保证(
数量 >= )
数量。也是为了防止最后一步没计算出来。(打个比方最后留下两个数字和一个操作符,会导致不能计算。19 ^6,这样的情况),所以加了)
可以强制计算19^6
。
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <stack>
using namespace std;
stack<int> nums;
stack<char> ops;
void cal(){
int a = nums.top(); nums.pop();
int b = nums.top(); nums.pop();
char c = ops.top(); ops.pop();
int d;
if (c == '+') d = b + a;
else if (c == '-') d = b - a;
else if (c == '*') d = b * a;
else if (c == '/') d = b / a;
else {
d = 1;
while (a --) d *= b;
}
nums.push(d);
}
int main(){
string str;
cin >> str;
// cout << str << endl;
if (str[0] == '-') str = '0' + str;
string left;
for (int i = 0; i < str.size(); i ++) left += '(';//先加左括号,变成合法前缀
str = left + str + ')';//加有括号,可以计算最后一步结果
for (int i = 0; i < str.size(); i ++){
if (str[i] >= '0' && str[i] <= '9'){//第一个字符是数字开头的话
int j = i, t = 0;
while (str[j] >= '0' && str[j] <= '9'){
t = t * 10 + str[j] - '0';
j ++;
}
nums.push(t);
i = j - 1;
}else{//其他符号开头
char c = str[i];
if (c == '(') ops.push(c);
else if (c == '+' || c == '-'){//如果是 + -
if (c == '-' && i && !(str[i - 1] >= '0' && str[i - 1] <= '9') && str[i - 1] != ')'){//-号需要特判,如果这个-表示负数,而不是减号
if (str[i + 1] == '('){
nums.push(-1);
ops.push('*');
}else{
int j = i + 1, t = 0;
while (str[j] >= '0' && str[j] <= '9'){
t = t * 10 + str[j] - '0';
j ++;
}
nums.push(-t);
i = j - 1;
}
}
else{//由于+ -优先级最低,如果栈里有其他运算符,直接计算
while (ops.top() != '(') cal();
ops.push(c);
}
}
else if (c == '*' || c == '/'){//当前符号是 * /,
while (ops.top() == '*' || ops.top() == '/' || ops.top() == '^') cal();
ops.push(c);
}
else if (c == '^'){//当前符号是^
while (ops.top() == '^') cal();
ops.push(c);
}
else if (c == ')'){//当前符号是)
while (ops.top() != '(') cal();
ops.pop();
}
else cout << "invalid operator!" << endl;
}
}
cout << nums.top() << endl;
return 0;
}