题目链接：
https://ac.nowcoder.com/acm/problem/50999
题面：
给出一个表达式,其中运算符仅包含+,-,*,/,^（加 减 乘 整除 乘方）要求求出表达式的最终值
数据可能会出现括号情况，还有可能出现多余括号情况
数据保证不会出现\geq 2^{31}的答案数据保证不会出现 ≥ 2^31 的答案
数据可能会出现负数情况
递归方案解答（完美AC）：
#include<iostream>
#include<cstring>
#include<math.h>
#include<algorithm>
using namespace std;
// 递归实现
string s;
int nums(int l, int r) {
int cnt = 0;
for (int i = l; i <= r; i++)
cnt = cnt * 10 + (s[i] - '0');
return cnt;
}
int calc(int l, int r) {
if (l > r) return 0;
int pos1 = -1, pos2 = -1, pos3 = -1; // ops1 : +- ; pos2 : */ ; pos3 : ^
int cnt = 0; // 标记左右括号
for (int i = l; i <= r; i++) {
// 统计当前范围内的括号个数
if (s[i] == '(') cnt++;
if (s[i] == ')') cnt--;
// 定位这个范围内相应运算符号最后一次出现的地点（越早被定位，递归深度越浅，越晚被执行运算）
// 这里是从递归角度出发确定相同优先级的运算符的执行顺序
if ((s[i] == '+' || s[i] == '-') && cnt == 0) pos1 = i;
if ((s[i] == '*' || s[i] == '/') && cnt == 0) pos2 = i;
if (s[i] == '^' && cnt == 0) pos3 = i;
}
// 在当前范围内没有符号的情况下，进行条件判断
if (pos1 == -1 && pos2 == -1 && pos3 == -1) {
//// 多余括号情况
// 左括号多余
if (cnt > 0 && s[l] == '(') return calc(l+1, r);
// 右括号多余
else if (cnt < 0 && s[r] == ')') return calc(l, r-1);
//// cnt == 0, 说明要么是数字，要么有一对括号括住它
else if (cnt == 0 && s[l] == '(' && s[r] == ')') return calc(l+1, r-1);
else return nums(l, r);
}
// 按优先级递归
if (pos1 != -1) { // + - 优先级最低
if (s[pos1] == '+') return calc(l, pos1-1) + calc(pos1+1, r);
if (s[pos1] == '-') return calc(l, pos1-1) - calc(pos1+1, r);
}
else if (pos2 != -1) { // * / 优先级中等
if (s[pos2] == '*') return calc(l, pos2-1) * calc(pos2+1, r);
if (s[pos2] == '/') return calc(l, pos2-1) / calc(pos2+1, r);
}
else if (pos3 != -1) { // ^ 优先级最高
return (int)pow(calc(l, pos3-1), calc(pos3+1, r));
}
return 0; // 编译器版本问题，需要加上这句
}
int main () {
cin >> s;
cout << calc(0, s.length()-1);
}
（非递归）栈方案解答，要考虑的情况多（不太完美，样例数据强度不行，但是AC）：
先利用两个栈（符号栈，结果栈）把输入的中缀表达式转成后缀表达式，再利用一个数据缓存栈计算后缀表达式。
中缀表达式转后缀表达式的常规思路归纳整理
(1) 初始化两个栈：运算符栈S1和储存中间结果的栈S2；
(2) 从左至右扫描中缀表达式；
(3) 遇到操作数时，将其压入S2；
(4) 遇到运算符时，比较其与S1栈顶运算符的优先级：
(4-1) 如果S1为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈；
(4-2) 否则，若优先级比栈顶运算符的高，也将运算符压入S1（注意转换为前缀表达式时是优先级较高或相同，而这里则不包括相同的情况）；
(4-3) 否则，将S1栈顶的运算符弹出并压入到S2中，再次转到(4-1)与S1中新的栈顶运算符相比较；
(5) 遇到括号时：
(5-1) 如果是左括号“(”，则直接压入S1；
(5-2) 如果是右括号“)”，则依次弹出S1栈顶的运算符，并压入S2，直到遇到左括号为止，此时将这一对括号丢弃；
(6) 重复步骤(2)至(5)，直到表达式的最右边；
(7) 将S1中剩余的运算符依次弹出并压入S2；
(8) 依次弹出S2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式（转换为前缀表达式时不用逆序）。
代码草稿（有待优化）：
#include<iostream>
#include<cstring>
#include<stack>
#include<map>
#include<vector>
#include<algorithm>
#include<functional>
using namespace std;
map<char, int> op = {
{'+', 1}, {'-', 1},
{'*', 2}, {'/', 2}, {'^', 3},
{'(', 0}, {')', 0}
};
/*
注意点1：
数字大小，要考虑十位百位千位的数据之间运算
注意点2：
数据可能会出现括号情况，还有可能出现多余括号情况
举例：
（（（（（1+4*5）此时左括号可以删去
（1+4*5））））））右括号可以删去
注意点3：
数据可能会有负数的情况
举例：
样例输入：
-123
(-123)
((-123)
(-123))))
-(123)
1+(-2)
1+(-2)*2+3
1+((-2)*2+3
1+(-2)*2+3
本题目前不太会用栈来实现
因为括号的问题和minus负数的问题
即使是正确的表达式，虽然题目是AC了，但是这是样例的强度不够
(-((-2+(-2))))^(1+1)
本代码没有考虑括号对齐的情况
*/
int main () {
string s;
cin >> s;
// 中缀表达式转后缀表达式，同时去除/清理括号
stack<char> op_st;
stack<string> hou_st;
int flag = 0;
int ptr_l_kuohao[35] = {}; //
for (int i = 0; i < s.length(); i++) {
// s[i] 是数字
if (s[i] >= '0' && s[i] <= '9') {
string nums;
while (s[i] >= '0' && s[i] <= '9' && i < s.length()) {
nums.push_back(s[i++]);
}
i--;
hou_st.push(nums);
// cout << "i : " << i << " nums : " << nums << endl;
}
else { // s[i] 是符号
if (s[i] == '(') { // 要排除孤儿左括号的影响
int ptr_r = i+1;
while(ptr_r < s.length()) { // 查询是否有和当前左括号匹配的最近的右括号，注意不要和后面的左括号冲突
if (s[ptr_r] == '(') {
ptr_r = s.length();
break;
}
if (s[ptr_r] == ')' && ptr_l_kuohao[ptr_r] == 0) {
ptr_l_kuohao[ptr_r] = 1;
break;
}
ptr_r++;
}
if (ptr_r != s.length()) { // 符号栈只存储非孤儿的左括号
op_st.push('(');
flag++;
}
cout << "i : " << i << " 102 first op : " << s[i] << endl;
}
else if (op_st.empty()) { // 符号栈为空
op_st.push(s[i]);
// cout << "i : " << i << " 107 op : " << s[i] << endl;
}
else if (s[i] == '+' || s[i] == '-' || s[i] == '*' || s[i] == '/' || s[i] == '^') {
if (s[i] == '-') {
if (s[i-1] == '(' || i == 0) { // 判定是否为负数 minus
if (s[i+1] >= '0' && s[i+1] <= '9') {
i++;
string nums;
nums.append("-");
while (s[i] >= '0' && s[i] <= '9' && i < s.length()) {
nums.push_back(s[i++]);
}
i--;
hou_st.push(nums);
// cout << "i : " << i << " 123 op-nums : " << nums << endl;
}
}
if (s[i+1] == ')') {
op_st.pop();
i++;
flag--;
continue;
}
}
// 当前访问的运算符优先级大于符号栈顶的，把当前访问的存入符号栈顶
if (op[s[i]] > op[op_st.top()]) {
op_st.push(s[i]);
cout << "i : " << i << " 142 op push : " << s[i] << endl;
}
// 当前访问的运算符优先级小于等于符号栈栈顶，
else if (op[s[i]] <= op[op_st.top()]) {
while (!op_st.empty() && op[s[i]] <= op[op_st.top()]) {
if (op_st.top() != '(') {
string opera;
opera.push_back(op_st.top());
hou_st.push(opera);
// cout << "i : " << i << " after pop <= next op : " << s[i] << endl;
}
op_st.pop();
}
op_st.push(s[i]);
}
}
else if (s[i] == ')' && flag > 0) { // 有左括号 使flag-- 才能有右括号执行下面的代码
while(op_st.top() != '('){
string opera;
opera.push_back(op_st.top());
hou_st.push(opera);
op_st.pop();
// cout << "i : " << i << " ( flag : " << flag << endl;
}
if (!op_st.empty()) { // 防止孤儿左括号（此处可以不用）
flag--;
op_st.pop(); // 把符号栈中的左括号弹出
}
}
}
// cout << "i : " << i << " ";
// cout << "打印 op_st : ";
// stack<char> tmp_op_st = op_st;
// while (!tmp_op_st.empty()) {
// cout << tmp_op_st.top() << " ";
// tmp_op_st.pop();
// }
//
// cout << endl << "打印 hou_st : " << endl;
// stack<string> tmp_hou_st = hou_st;
// while (!tmp_hou_st.empty()) {
// cout << tmp_hou_st.top() << " ";
// tmp_hou_st.pop();
// }
//
// cout << endl;
}
while(!op_st.empty()) {
if (op_st.top() != '(' || op_st.top() != ')') {
string remain;
remain.push_back(op_st.top());
hou_st.push(remain);
}
op_st.pop();
}
vector<string> hou;
while (!hou_st.empty()) {
// if (hou_st.top() != "(" || hou_st.top() != ")") {
hou.push_back(hou_st.top());
// }
hou_st.pop();
}
reverse(hou.begin(), hou.end());
// cout << endl << endl;
// cout << "中缀转后缀："<< endl;
// for (auto a : hou) {
// cout << a << " ";
// }
// cout << endl << endl;
// 测试数据
// 2+2^4/8-6 --> 234^/8-6 --> -2
// (2+2)^(1+1) --> 22+11+^ --> 16
// 3+(2*5+7^2)-6*(3+2) --> 32
// 123+444*2^2/111-24 --> 115
// 100-5*5^(1+2)/5+25 --> 0
// 后缀表达式入栈计算
// 只要（数字+中间结果）栈 即可
stack<long long> ans_st;
function<long long(string)> calc = [&](string nums) {
long long res = 0;
if (nums[0] != '-') {
for (int i = 0; i < nums.length(); i++) {
res = res * 10 + (nums[i] - '0');
}
}
else {
for (int i = 1; i < nums.length(); i++) {
res = res * 10 + (nums[i] - '0');
}
res = -res;
}
return res;
};
for (int i = 0; i < hou.size(); i++) {
if (hou[i] == "(" || hou[i] == ")") continue;
if (hou[i][0] >= '0' && hou[i][0] <= '9' || hou[i].length() >= 2) {
ans_st.push(calc(hou[i]));
}
else { // 五种符号
long long l = 0, r = 0, tmp = 0;
r = ans_st.top();
ans_st.pop();
if (!ans_st.empty()) { // 防范 负数样例 -123
l = ans_st.top();
ans_st.pop();
}
if (hou[i][0] == '+') {
tmp = l + r;
}
else if (hou[i][0] == '-') {
tmp = l - r;
}
else if (hou[i][0] == '*') {
tmp = l * r;
}
else if (hou[i][0] == '/') {
tmp = l / r;
}
else if (hou[i][0] == '^') {
tmp = 1;
for (int j = 0; j < r; j++) {
tmp *= l;
}
}
ans_st.push(tmp);
// cout << hou[i] << " : ";
// // 状态打印
// stack<long long> tmp_ans_st = ans_st;
// while(!tmp_ans_st.empty()){
// cout << tmp_ans_st.top() << " ";
// tmp_ans_st.pop();
// }
// cout << endl;
}
}
cout << ans_st.top();
}
京公网安备 11010502036488号