问题 M: 中缀表达式转后缀表达式

#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.最终将栈中的元素依次出栈,输出。 

上一篇:简易机器翻译器


下一篇:Libevent源码学习笔记一:event2/event.h