将中缀表达式转化成后缀表达式_中缀表达式转后缀表达式

中缀变后缀主要的思想就是将需要的运算符先做一个映射

 对于任意表达式，式中从头开始扫，遇到非运算符，即任意数字或字母直接输出

遇到运算符考虑放入栈中

若栈空则放入

若栈不为空，判断栈顶的优先级是否 < 待放入的运算符，若 小于则将其压入栈中；

若不小于，则将栈一直 pop，知道运算符可以放入栈中

当然还有特殊的元素符, '('   ')'  这两个元素比较特殊，‘（’ 元素符优先级最大，自然放入栈中，但是要注意，只有遇到 ')' 时，‘（’

才会弹出，所以在栈中有 '(' 时，需要特判，当然 '('  ')' 这两个运算符是不需要输出的

下面给出应用 STL 中的程序和自己写的栈链的程序，主函数是相似的，只是在不重要的地方改了一下

stack 代码：

#include <iostream>
#include <map>
#include <stack>
using namespace std;
 
    int n,m,t;
    int i,j,k;
    //int a[N];
    map<char,int> mp;
 
int main()
{
    //IOS;
    mp['+']=mp['-']=1;
    mp['*']=mp['/']=2;
    mp['(']=3,mp[')']=1;
 
    stack<char> s;
    while(s.size()) s.pop();
    string str; cin>>str;
    for(int i=0;str[i];i++){
        //dbg(i);
        if(!mp.count(str[i])) cout<<str[i];
        else{ //处理运算符
            if(s.empty()) s.push(str[i]);
            else
            {
                if(mp[str[i]]<=mp[s.top()] && s.top()=='('){
                    s.push(str[i]);
                }
                else if(str[i]==')'){
                    while(true){
                        if(s.size() && s.top()=='(') { s.pop(); break; }
                        else if(s.size()) cout<<s.top(),s.pop();
                    }
                }
                else if(mp[str[i]]>mp[s.top()]) s.push(str[i]);
                else{
                    while(true){
                        if(s.size() && s.top()=='(') { s.push(str[i]); break; }
                        if(s.empty() || mp[str[i]]>mp[s.top()]){ s.push(str[i]); break; }
                        else cout<<s.top(),s.pop();
                    }
                }
            }
        }
    }
    while(s.size()) cout<<s.top(),s.pop();
    cout<<endl;
    //PAUSE;
    return 0;
}

手写栈链代码 ：

#include <iostream>
#include <map>
#define null NULL
using namespace std;
    int n,m,t;
    int i,j,k;
    //int a[N];
    map<char,int> mp;
 
    struct node
    {
        char data;
        node *next;
    };
 
class Stack
{
private:
    node *fa;
    int sum;
public:
    Stack ()
    {
        fa=new node;
        fa=null;
        sum=0;
    }
    void push(char x)
    {
        node *p=new node;
        p->data=x;
        p->next=fa;
        fa=p;
        sum++;
    }
    void pop()
    {
        node *p=fa;
        fa=fa->next;
        delete p;
        sum--;
    }
    char top()
    {
        return fa->data;
    }
    bool empty()
    {
        if(fa==null) return true;
        else return false;
    }
    int size()
    {
        return sum;
    }
};
 
int main()
{
    //IOS;
    mp['+']=mp['-']=1;
    mp['*']=mp['/']=2;
    mp['(']=3,mp[')']=1;
 
    Stack s;
    while(s.size()) s.pop();
    char str[100]; cin>>str;
    for(int i=0;str[i];i++){
        //dbg(i);
        if(!mp.count(str[i])) cout<<str[i];
        else{ //处理运算符
            if(s.empty()) s.push(str[i]);
            else
            {
                if(mp[str[i]]<=mp[s.top()] && s.top()=='('){
                    s.push(str[i]);
                }
                else if(str[i]==')'){
                    while(true){
                        if(s.size() && s.top()=='(') { s.pop(); break; }
                        else if(s.size()) cout<<s.top(),s.pop();
                    }
                }
                else if(mp[str[i]]>mp[s.top()]) s.push(str[i]);
                else{
                    while(true){
                        if(s.size() && s.top()=='(') { s.push(str[i]); break; }
                        if(s.empty() || mp[str[i]]>mp[s.top()]){ s.push(str[i]); break; }
                        else cout<<s.top(),s.pop();
                    }
                }
            }
        }
    }
    while(s.size()) cout<<s.top(),s.pop();
    cout<<endl;
    //PAUSE;
    return 0;
}