C++后缀表达式

引进概念

中缀表达式：即一般的表达式

  eg. a+b*c/d*(e-f)

后缀表达式：即将中缀表达式中的运算符置于操作的数字后

  eg. abc*d/ef-*+

中缀表达式–>后缀表达式

运用一个栈，一个队列，分别用来 临时 存放运算符和存放 后缀表达式 ，分别记为和。

1. 从左到右遍历字符串
2. 取到数字则直接加入队列中
3. 取到运算符的情况如下：
   • 若栈为空，则直接放入队列
   • 若取到字符是 ‘ ( ‘ (最低级) ，直接放入
   • 否则与栈顶比较运算符优先级，优先与栈顶则放入，否则
     循环，弹出栈顶元素并放入队列中，直到栈顶优先级较小(不相等)为止
   • 若取出字符是 ‘ ) ‘ 则一直弹出并入队到 ‘ ( ‘ 并舍弃 ‘ ( ‘ ，’ ) ‘ 其中 ‘ ( ‘ 不入队

#include<iostream>
#include<algorithm>
#include<cstring>
#include<stack>
#include<queue>
using namespace std;
int l=1;
char a[1000000];
stack <char> s;
queue <char> q;

int pri(char op)
{
    if(op=='+'||op=='-') return 1;
    else if(op=='*'||op=='/') return 2;
    else if(op=='(') return 0;
}

int main()
{
    while((a[l++]=getchar())!='\n'&&a[l]!=' ');
    for(int i=1;i<=l;i++)
    {
        if(a[i]>='0'&&a[i]<='9') q.push(a[i]);
        else if(!s.size()) s.push(a[i]);
        else if(a[i]=='(') s.push(a[i]);
        else if(a[i]=='+'||a[i]=='-'||a[i]=='*'||a[i]=='/') 
        {
            while(pri(s.top())>pri(a[i])) 
            {
                q.push(s.top());
                s.pop();
                if(!s.size()) break; 
            }
            s.push(a[i]);
        }
        else if(a[i]==')')
        {
            while(s.top()!='(')
            {
                q.push(s.top());
                s.pop();
            }
            s.pop();
        }
    }
    while(s.size()) 
    {
        q.push(s.top());
        s.pop();
    }
    while(q.size())
    {
        cout<<q.front();
        q.pop();
    }
    return 0;
}

运用——后缀表达式求值

此运算的实现需运用一个栈用来存操作的数字，记为。可用于非一般操作的运算式 (如 & | ！的逻辑运算) 求值。

1. 将中缀表达式转化为后缀表达式
2. 遍历后缀表达式，遇到数字则放入中
3. 若取出运算符，则从中取出两个元素，进行计算后将值放入中

while(q.size()) // q 是存后缀表达式的队列
{
    if(q.front()>='0'&&q.front()<='9') s.push(q.front()-'0');
    else if(q.front()=='+') 
    {
        int n1=s.top();
        s.pop();
        int n2=s.top();
        s.pop();
        s.push(n1+n2);
    }
    else if(q.front()=='-')
    {
        int n1=s.top();
        s.pop();
        int n2=s.top();
        s.pop();
        s.push(n1-n2);
    }
    else if(q.front()=='*')
    {
        int n1=s.top();
        s.pop();
        int n2=s.top();
        s.pop();
        s.push(n1*n2);
    }
    else 
    {
        int n1=s.top();
        s.pop();
        int n2=s.top();
        s.pop();
        s.push(n1/n2);
    }
    q.pop();
}
printf("%d",s.top());