#include <iostream>
#include <cstdio>
#include <stack>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
//-1不需要删,1需要删
int SignCompare(char ch1, char ch2){
if(ch1 == '+' && ch2 == '*') return -1;
if(ch1 == '*' && ch2 == '+') return 1;
if(ch1 == '+' && ch2 == '/') return -1;
if(ch1 == '/' && ch2 == '+') return 1;
if(ch1 == '-' && ch2 == '*') return -1;
if(ch1 == '*' && ch2 == '-') return 1;
if(ch1 == '-' && ch2 == '/') return -1;
if(ch1 == '/' && ch2 == '-') return 1;
if(ch1 == '+' && ch2 == '-') return 1;
if(ch1 == '-' && ch2 == '+') return 1;
if(ch1 == '*' && ch2 == '/') return 1;
if(ch1 == '/' && ch2 == '*') return 1;
if(ch1 == ch2)return 1;
}
int main()
{
stack<char> st;
string s;
getline(cin, s);
for(int i = 0; i < s.size(); i++){
//元素是操作数则直接输出
if((s[i] >= 'A' && s[i] <= 'Z') || (s[i] >= 'a' && s[i] <= 'z')){
cout<<s[i];
}
else if(s[i] == '(' || s[i] == '*' || s[i] == '/' || s[i] == '+' || s[i] == '-'){
//栈空则直接推入
if(st.empty() || s[i] == '(')st.push(s[i]);
//弹出所有优先级大于或者等于该运算符的*栈顶*元素,然后将该运算符入栈
else{
//栈顶符号优先度小于s[i]
if(SignCompare(st.top(), s[i]) < 0) st.push(s[i]);
//栈顶元素大于等于s[i]
else{
while(!st.empty() && SignCompare(st.top(), s[i]) > 0){
if(st.top() == '(')break;
cout<<st.top();
st.pop();
}
st.push(s[i]);
}
}
}
//s[i]为右括号时不断弹出,并输入操作符,直到遇到左括号就停止
else if(s[i] == ')'){
while(!st.empty()){
if(st.top() != '(')cout<<st.top();
else if(st.top() == '('){
st.pop();
break;
}
st.pop();
}
}
}
//最后输出栈中剩余元素
while(!st.empty()){
cout<<st.top();
st.pop();
}
return 0;
}
中缀表达式转后缀表达式的方法:
1.遇到操作数:直接输出(添加到后缀表达式中)
2.栈为空时,遇到运算符,直接入栈
3.遇到左括号:将其入栈
4.遇到右括号:执行出栈操作,并将出栈的元素输出,直到弹出栈的是左括号,括号不输出。
5.遇到其他运算符:加减乘除:弹出所有优先级大于或者等于该运算符的栈顶元素,然后将该运算符入栈
6.最终将栈中的元素依次出栈,输出。