省流：毒瘤字符串
题目传送门
没事中间加个转中缀干嘛？害的我当年调了一上午。
这个就是栈的经典板子后缀表达式的一个加强版，需要先中缀转后缀再求答案。
灵活变通，压两个栈不就行了。
中缀转后缀：
string zhongzhui(string s){mp['+'] = 1;mp['-'] = 2;mp['*'] = 3;mp['/'] = 4;mp['('] = 5;mp[')'] = 6;mp['^'] = 7;for (int i = 1; i <= 9; i++)for (int j = 1; j <= 9; j++)b[i][j] = 0;b[5][5] = 1; b[7][7] = 1; b[1][3] = 1; b[1][4] = 1; b[1][5] = 1; b[1][7] = 1; b[2][3] = 1; b[2][4] = 1; b[2][5] = 1;b[2][7] = 1; b[3][5] = 1; b[3][7] = 1; b[4][5] = 1; b[4][7] = 1; b[5][1] = 1; b[5][2] = 1; b[5][3] = 1; b[5][4] = 1;b[5][6] = 1; b[5][7] = 1; b[6][1] = 1; b[6][2] = 1; b[6][3] = 1; b[6][4] = 1; b[6][5] = 1; b[6][7] = 1; b[7][5] = 1; // 小小打表string ans;char a[35] = "";int num = 0, sum = 0;for (int i = 0; i < s.size(); i++)if (s[i] >= '0' && s[i] <= '9')num = num * 10 + s[i] - 48;else {if (num > 0){string str = "";while (num > 0)str = char(num % 10 + '0') + str, num /= 10;ans = ans + str + ' ';}if (s[i] == ')') // 关于括号的处理while(1){if (sum <= 0)break;if (a[sum] == '('){sum--;break;}ans = ans + a[sum] + ' ';sum--;}else{while(sum > 0 && b[mp[a[sum]]][mp[s[i]]] == 0)ans = ans + a[sum] + ' ', sum--;a[++sum] = s[i];}}if (num > 0){string str = "";while (num > 0)str = char(num % 10 + '0') + str, num /= 10;ans = ans + str + ' ';}while (1){ans = ans + a[sum] + ' ';sum--;if (sum <= 0)break;}return ans;
}
后缀求答案：
void getans(string s){ // 橙cout << s << endl;int x = 0, sum = 0, a[100005] = {0};for (int i = 0; i < s.size(); i++){if (s[i] >= '0' && s[i] <= '9')x = x * 10 + s[i] - 48;else if (s[i] == ' ' && x > 0)a[++sum] = x, x = 0;else{if (s[i] == ' ')continue;if (s[i] == '+')a[sum - 1] += a[sum], sum--;else if (s[i] == '-')a[sum - 1] -= a[sum], sum--;else if (s[i] == '*')a[sum - 1] *= a[sum], sum--;else if (s[i] == '/')a[sum - 1] /= a[sum], sum--;else if (s[i] == '^')a[sum - 1] = pow(a[sum - 1], a[sum]), sum--;for (int i = 1; i < sum; i++)cout << a[i] << ' ';cout << a[sum];cout << s.substr(i + 1) << endl;;}}
}
所以橙+黄=绿。
code
#include<bits/stdc++.h>
using namespace std;string s;
map <char, int> mp;
int b[10][10];void getans(string s){cout << s << endl;int x = 0, sum = 0, a[100005] = {0};for (int i = 0; i < s.size(); i++){if (s[i] >= '0' && s[i] <= '9')x = x * 10 + s[i] - 48;else if (s[i] == ' ' && x > 0)a[++sum] = x, x = 0;else{if (s[i] == ' ')continue;if (s[i] == '+')a[sum - 1] += a[sum], sum--;else if (s[i] == '-')a[sum - 1] -= a[sum], sum--;else if (s[i] == '*')a[sum - 1] *= a[sum], sum--;else if (s[i] == '/')a[sum - 1] /= a[sum], sum--;else if (s[i] == '^')a[sum - 1] = pow(a[sum - 1], a[sum]), sum--;for (int i = 1; i < sum; i++)cout << a[i] << ' ';cout << a[sum];cout << s.substr(i + 1) << endl;;}}
} string zhongzhui(string s){mp['+'] = 1;mp['-'] = 2;mp['*'] = 3;mp['/'] = 4;mp['('] = 5;mp[')'] = 6;mp['^'] = 7;for (int i = 1; i <= 9; i++)for (int j = 1; j <= 9; j++)b[i][j] = 0;b[5][5] = 1; b[7][7] = 1; b[1][3] = 1; b[1][4] = 1; b[1][5] = 1; b[1][7] = 1; b[2][3] = 1; b[2][4] = 1; b[2][5] = 1;b[2][7] = 1; b[3][5] = 1; b[3][7] = 1; b[4][5] = 1; b[4][7] = 1; b[5][1] = 1; b[5][2] = 1; b[5][3] = 1; b[5][4] = 1;b[5][6] = 1; b[5][7] = 1; b[6][1] = 1; b[6][2] = 1; b[6][3] = 1; b[6][4] = 1; b[6][5] = 1; b[6][7] = 1; b[7][5] = 1;string ans;char a[35] = "";int num = 0, sum = 0;for (int i = 0; i < s.size(); i++)if (s[i] >= '0' && s[i] <= '9')num = num * 10 + s[i] - 48;else {if (num > 0){string str = "";while (num > 0)str = char(num % 10 + '0') + str, num /= 10;ans = ans + str + ' ';}if (s[i] == ')')while(1){if (sum <= 0)break;if (a[sum] == '('){sum--;break;}ans = ans + a[sum] + ' ';sum--;}else{while(sum > 0 && b[mp[a[sum]]][mp[s[i]]] == 0)ans = ans + a[sum] + ' ', sum--;a[++sum] = s[i];}}if (num > 0){string str = "";while (num > 0)str = char(num % 10 + '0') + str, num /= 10;ans = ans + str + ' ';}while (1){ans = ans + a[sum] + ' ';sum--;if (sum <= 0)break;}return ans;
}int main() {cin >> s;getans(zhongzhui(s));return 0;
}