逆波兰表达式 （中缀转换位后缀）

//#include <bits/stdc++.h> #include<map> #include<iostream> #include<stack> #include<vector> using namespace std; const int maxn = 1e4 + 10; typedef long long ll; stack<char> sta; // sta是用来存各种符号的（正负除外，正负号会作为数字的一部分和数字一起被输出） int main() { map<char, int> mp; string str; cin >> str; bool isfirst = true; mp['-'] = 1, mp['+'] = 1; mp['*'] = 2, mp['/'] = 2; mp['('] = 3, mp[')'] = 3; for (int i = 0; i < str.size(); i++) { // + - 号的含义为正负号的时候 或者 是当前位置上的元素为数字 或者 小数点的情况 if (((i == 0 || str[i - 1] == '(') && (str[i] == '+' || str[i] == '-')) || (str[i] >= '0' && str[i] <= '9')) { if (!isfirst)// 如果不是第一次打印 就输出前导的空格 { cout << " "; } if (str[i] != '+') // 正号不进行输出 { cout << str[i]; } //将当前所搜索到的数字进行全部输出（包括小数）（遇到数字直接进行输出） while (str[i + 1] == '.' || (str[i + 1] >= '0' && str[i + 1] <= '9')) // 将小数点后面的位数 或者 是多位数进行全部地输出 { i++; cout << str[i]; } isfirst = false; // 首次输出的标志逆转 } else { if (str[i] == ')') // 如果现在搜索到的元素是右括号 { //如果sta栈还没有被弹空 （防止访问越界），且sta栈的栈顶还不是左边的括号 while (!sta.empty() && sta.top() != '(') { //括号内的运算符都是有序的，可以直接输出 cout << ' ' << sta.top(); sta.pop(); } sta.pop(); // 左边的括号也要弹出 } else if (sta.empty() || mp[str[i]] > mp[sta.top()]) // 如果当前的运算符的优先级要高于栈顶的运算符的优先级，就可以直接压入 { sta.push(str[i]); } else { while (!sta.empty() && sta.top() != '(') // 当前的栈顶运算符号的优先级较低 （则将括号中的所有运算符号都弹出 没有括号则直接弹空（都是些升序排列的运算符）） { cout << ' ' << sta.top(); sta.pop(); } sta.push(str[i]); } } } while (!sta.empty()) // 输出剩下的一些运算符号 { cout << ' ' << sta.top(); sta.pop(); } return 0; }