猫史档案馆

用户:

SCS_user_EHQ0z2l6el查看:6 回复:4 评论:6 创建时间:2023-04-21T13:34:35

上次讲了如何计算后缀表达式

而日常生活中我们使用的是中缀表达式

比如

9 + (3 − 1) ∗ 3 + 10/2（上次的算式）

转后缀表达式就是

9 3 1 − 3 ∗ + 10 2 / +

话不多说，我们直接来看中缀如何转后缀吧

中缀转后缀五步

1.从中缀表达式的左边开始扫描，若遇到运算数，则直接将其输出(不压入栈)

2.若遇到左括号，则将其压栈（喵压入条件1:左括号）

3.若遇到右括号，表示中缀表达式括号内的东西已经扫描完毕

这时需将栈顶的运算符依次弹出并输出，

直至遇到左括号（左括号弹出但不输出）（一波了）

4.若遇到的是运算符:

4-1.如果该运算符的优先级大于栈顶运算符的优先级时，将其压栈（喵压入条件二）

4-2.如果该运算符的优先级小于栈顶运算符的优先级时，将栈顶运算符弹出并输出，

接着和新的栈顶运算符比较，若大于，则将其压栈，若小于，继续将栈顶运算符弹出并输出

(一直递归下去，直至运算符大于栈顶运算符为止)

5.最后一步，若扫描到中缀表达式的末尾（即扫描结束），若堆栈中还有存留的运算符依次弹出并输出即可

（还有一点，就是栈空，这时候可以喵压入）

看到这里可能大家都要打盹了

我们打个比方

9 + (3 − 1) ∗ 3 + 10/2如何转后缀

1.首先从左往右扫描

首先遇到的是 9，根据规则1，我们直接输出

输出：9

2.遇到的第二个是 +，我们直接喵压入栈

栈[ + ]//为了方便演示，这里不打双引号

3.接下来遇到了左括号，根据规则2，喵压入栈

[ + , ( ]

4.一直到右括号，此时的输出和栈内元素是这样的

[ + , ( , - ]

输出：9 3 1

5.遇到右括号，直接一波，输出栈内元素一直到左括号

[ + ]

输出：9 3 1 -

6.遇到“*”，比+优先级大，喵压

[ + , * ]

7.接下来是 + ，根据4.2，+的优先级比*小，我们输出*，然后输出+（栈里的+和+比较的话是左边的大）

接着栈空，喵压入+

[ + ]

输出：9 3 1 − 3 ∗ +

8.遍历到最后，栈里只剩下“/”和“+”元素，直接输出

输出：9 3 1 − 3 ∗ + 10 2 / +

这就是中转后的全过程

代码的话我会放在评论区，想要的可以去翻翻。

再见awa

SCS_user_EHQ0z2l6el

//中转后缀表达式
#include<iostream>
#include<cstdio>
#include<stack>
using namespace std;
stack <char> s;//栈
char popfront(){
    char a=s.top();
    s.pop();
    return a;
}
int pri(char a){
    switch(a){
        case '(':
        case ')':return 0;
        case '+':
        case '-':return 1;
        case '*':
        case '/':return 2;
    }
    return 0;
}
int main(){
    string x;
    cin>>x;
    for(int i=0;i<x.size();i++){
        if('0'<=x[i]&&x[i]<='9'){
            int num=0;
            while(1){
                num*=10;
                num+=x[i]-'0';
                if((i+1>=x.size())||('0'>x[i+1]||x[i+1]>'9')){
                    break;
                }
                i++;
            }
            cout<<num<<" ";
            continue;
        }
        //后面就是符号处理
        if(x[i]=='('||s.empty()||(!s.empty() && pri(s.top())<pri(x[i]))){//无脑压入条件：左括号，栈为空，栈顶符号优先级小于当前符号
            s.push(x[i]);
        }else if(x[i]==')'){
            while(s.top()!='(')
                cout<<popfront()<<" ";
            s.pop();
        }else{
            while(s.size()&&pri(s.top())>=pri(x[i]))
                cout<<popfront()<<" ";
            s.push(x[i]);
        }
    }
    while(!s.empty()){
        cout<<popfront()<<" ";
    }
    return 0;
}

SCS_user_EHQ0z2l6el

怎么计算后缀表达式：https://shequ.codemao.cn/community/534701

SCS_user_EHQ0z2l6el

下期想看什么记得评论哦～（红黑树不行）

𝙲ℴ𝗌𝔦𝒹ₑ𝑟

如果只看形式不考虑实现：

后缀运算模式把运算的数字置于前

9 + (3 − 1) ∗ 3 + 10/2

只需要根据优先顺序

( 9 + ( (3 − 1) ∗ 3 ) 10/2 )+

把运算符移至对应操作数字的后面

......（故意懒（）

{ ( ( 9 [ ( 3 1 -) 3 * ] ) ( 10 2 / ) ) +} +

9 3 1 - 3 * + 10 2 / +

（注：括号表示优先级，不参与示例中后缀运算）

猫史档案馆

中缀转后缀思路（c++教学）

回复