18图灵班作业13：中缀式转换为逆波兰表达式

代码实现:

#include <vector>
#include <stack>
#include <iostream>
#include <map>
using namespace std;
stack<int> t1;
stack<char> t2;
map<char,int> priority;
int toInt(string goal){
    int ans=0;
    for(int i=0;i<goal.size();i++){
        ans*=10;
        ans+=goal[i]-'0';
    }
    return ans;
}
void initPriority(){
    priority['+']=1;
    priority['-']=1;
    priority['*']=2;
    priority['/']=2;
    priority['(']=0;
    priority[')']=0;
}
int main(){
    freopen("test.in","r",stdin);
    freopen("test.out","w",stdout);
    initPriority();
    string now;
    while(cin>>now){
        if(now=="*"||now=="/"||now=="+"||now=="-"||now=="("||now==")"){
            if(now=="("||t2.empty()){
                t2.push(now[0]);
                continue;
            }
            if(now==")"){
                while(t2.top()!='('){
                    char tmp=t2.top();
                    t2.pop();
                    cout<<tmp<<" ";
                }
                t2.pop();
                continue;
            }
            char nowTop=t2.top();
            if(priority[nowTop]<priority[now[0]]){
                t2.push(now[0]);
            }
            else{
                while(!t2.empty()&&priority[t2.top()]!=0&&priority[t2.top()]>=priority[now[0]]){
                    char tmp=t2.top();
                    t2.pop();
                    cout<<tmp;
                }
                t2.push(now[0]);
            }
            // if(now=="*"||now=="/"&&(t2.top()!='*'||t2.top()!='/')){
            //     t2.push(now[0]);
            // }
            // if(now=="+"||now=="-"){
            //     while(!t2.empty()&&(t2.top()=='*'||t2.top()=='/'||t2.top()=='+'||t2.top()=='-')){
            //         char tmp=t2.top();
            //         t2.pop();
            //         cout<<tmp;
            //     }
            //     t2.push(now[0]);
            // }
        }
        else{
            int tmp=toInt(now);
            cout<<tmp<<" ";
        }
    }
    while(!t2.empty()){
        char tmp=t2.top();
        t2.pop();
        cout<<tmp<<" ";
    }
}

思路

• 算法的思想是遇到数字直接输出，遇到运算符号时则把它保存在这个栈中。这个栈需要满足的一个特征时从栈顶到栈底，运算符顺序依次递减，从而在输出时保持优先级的正确。
• 当栈顶的运算符号优先级大于等于将要入栈的符号优先级时，将栈顶符号弹出并输出，直到满足第一点的特征。因为在栈中优先级是依次递减的，那么当新的运算符号优先级低于当前栈顶的优先符号时我们至少可以确定当前栈顶的符号要先于我们即将入栈的运算符号输出。PS：至于为什么当前的运算符号和栈顶的运算符号具有相同的优先级时也要输出是因为我们扫描符号的时候是从左往右的，优先级相同时就是先扫描到的符号（在栈顶的）先运算。
• 关于括号的问题：遇到括号就应该把括号内的运算式看做一个整体。相当于以左右括号为界，在栈中嵌套了一个栈。
• 最后用一个map来储存优先级是为了便于程序的拓展，毕竟可能会有其他不同优先级的运算符号加入进来。