PTA 天梯赛 L7-20：表达式转换 ← 中缀 to 后缀

​【题目来源】
https://pintia.cn/problem-sets/15/exam/problems/type/7?problemSetProblemId=827

【题目描述】
算术表达式有前缀表示法、中缀表示法和后缀表示法等形式。日常使用的算术表达式是采用中缀表示法，即二元运算符位于两个运算数中间。请设计程序将中缀表达式转换为后缀表达式。

【输入格式】
输入在一行中给出不含空格的中缀表达式，可包含+、-、*、/以及左右括号()，表达式不超过20个字符。

【输出格式】
在一行中输出转换后的后缀表达式，要求不同对象（运算数、运算符号）之间以空格分隔，但结尾不得有多余空格。

【输入样例】
2+3*(7-4)+8/4

【输出样例】
2 3 7 4 - * + 8 4 / +

【数据范围】
中缀表达式长度≤20

【算法分析】
● 本题坑点一，在于区分 '-' 是减号还是负数符号，'+' 是加号还是正数符号。
● 本题坑点二，在于将 '.' 视为操作数，而不是操作符。及将其视为数字。

【算法代码】

#include <bits/stdc++.h>
using namespace std;map<char,int> pri= {{'(',0}, {')',0},{'+',1}, {'-',1},{'*',2}, {'/',2}
};bool isNum(char c) {return isdigit(c) || c=='.';
}//Determine whether it is a [positive/negative sign]
bool isSign(string s,int i,char c) {return (i==0 || s[i-1]=='(') && (c=='+' || c=='-');
}string getNum(string s,int &i) {string t;if(s[i]!='+') t+=s[i];while(i+1<s.size() && isNum(s[i+1])) {t+=s[i+1];i++;}return t;
}//Handle the right parenthesis
void procRight(vector<string> &v,stack<char> &op) {while(op.top()!='(') {v.push_back({op.top()});op.pop();}op.pop();
}//Handle operators
void procOP(char c,vector<string> &v,stack<char> &op) {while(!op.empty() && pri[c]<=pri[op.top()]) {v.push_back({op.top()});op.pop();}op.push(c);
}int main() {string s;cin>>s;vector<string> v;stack<char> op;for(int i=0; i<s.size(); i++) {if(isNum(s[i]) || isSign(s,i,s[i])) {v.push_back(getNum(s,i));} else if(s[i]=='(') op.push(s[i]);else if(s[i]==')') procRight(v,op);else procOP(s[i],v,op);}while(!op.empty()) {v.push_back({op.top()});op.pop();}for(int i=0; i<v.size(); i++) {if(i) cout<<" ";cout<<v[i];}return 0;
}/*
in:2+3*(7-4)+8/4
out:2 3 7 4 - * + 8 4 / +
*/

【参考文献】
https://blog.csdn.net/weixin_45962741/article/details/113698836

 

​