1-3 表达式转换 (25分)（我的偶像是大佬）

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

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

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

输入样例:

2+3*(7-4)+8/4

输出样例:

2 3 7 4 - * + 8 4 / +

主要是逆波兰算法，即栈的应用，话不多说，反手就给偶像一个赞，偶像啥都会，，我的偶像是大佬。太强了！！！

#include <iostream> #include <stack> using namespace std; int main(){ ios::sync_with_stdio(false); cin.tie(0),cout.tie(0); string s; cin >> s; int len = 0; for(int i = 0;i<s.length();i++){ if(s[i]>='0'&&s[i]<='9'||s[i]=='.') len++; } if(len==s.length()){//只有一个数字 cout << s; return 0; } if(s[0]=='-'){//运算数前有负号 s = s.substr(1); cout << "-"; } stack<char> st;//运算符栈 string res; for(int i = 0;i<s.length();i++){ if(s[i]>='0'&&s[i]<='9'){//如果是数字就继续遍历，因为运算数不一定是一位 int j = i+1; while((s[j] >= '0' && s[j] <= '9'||s[j]=='.')) j++; res += s.substr(i,j-i); res += " "; i = j-1;//跳过所有已经遍历的数字，因为后边还要i++，所以 = j-1 }else{ char op = s[i]; if(op=='+'&&s[i-1]!='('||op=='-'&&s[i-1]!='('){//(后有正负号不入栈 while(!st.empty()&&st.top()!='('){ res += st.top(); res += " "; st.pop(); } st.push(op);//低优先级运算符最后入栈 }else if(op=='*'||op=='/'||op=='('){//高优先级直接入栈 st.push(op); }else if(op==')'){//弹栈，直到遇到左括号 while(st.top()!='('){ res += st.top(); res += " "; st.pop(); } st.pop();//弹出左括号，不输出 } } } while(!st.empty()){//如果栈内还有元素，全部出栈输出 res += st.top(); if(st.size()>1) res += " "; st.pop(); } cout << res; return 0; }