栈-表达式计算

表达式分类: 前缀，中缀(人类使用的方式)，后缀(计算机能够处理的方式)

后缀表达式求值

1. 建立一个用于存数的栈,逐一扫描该后缀表达式中的元素

2. 扫描表达式

   • 如果遇到一个数,则把该数入栈
   • 如果遇到运算符,就取出栈顶的两个数进行计算,把结果入栈

3. 扫描完成后,栈中恰好剩下一个数,就是该后缀表达式的值

代码如下

//数据结构
struct node{
    bool op;
    int val;
}a[100005];
stack <node> st;

//类型判断函数
inline int op(char c){
    if (c=='+') return 1;
    if (c=='-') return 2;
    if (c=='*') return 3;
    if (c=='/') return 4;
    if (c=='^') return 5;
    if (c=='(') return -1;
    if (c==')') return -2;
    return 0;
}

//Main函数
for (int i=1;i<=n;++i){
    if (!a[i].op){
        st.push(a[i]);
    }else{
        int x,y,c;
        y=st.top().val;st.pop();
        x=st.top().val;st.pop();
        if (a[i].val==1) c=x+y;
        if (a[i].val==2) c=x-y;
        if (a[i].val==3) c=x*y;
        if (a[i].val==4) c=x/y;
        if (a[i].val==5) c=pow(x,y);
        st.push({0,c});
    }
}

中缀表达式求值

1. 建立一个用于存运算符的栈

2. 扫描表达式

   • 如果遇到一个数,输出该数
   • 如果遇到左括号,把左括号入栈
   • 如果遇到右括号,不断取出栈顶并输出,直到栈顶为左括号,然后把左括号出栈
   • 如果遇到运算符,只要栈顶符号的优先级不低于新符号,就不断取出栈顶并输出,最后把新符号进栈(优先级为乘方>乘除>加减>左括号)

3. 依次取出并输出栈中的所有剩余符号,最终输出的序列就是一个与原中缀表达式等价的后缀表达式

完整代码如下，包含字符处理

原题链接

#include <bits/stdc++.h>
using namespace std;

struct node{
    bool op;
    int val;
}a[100005];
char s[100005];
int n,cnt;
stack <node> st;

inline int op(char c){
    if (c=='+') return 1;
    if (c=='-') return 2;
    if (c=='*') return 3;
    if (c=='/') return 4;
    if (c=='^') return 5;
    if (c=='(') return -1;
    if (c==')') return -2;
    return 0;
}

inline int lv(int c){
    if (c==1||c==2) return 1;
    if (c==3||c==4) return 2;
    if (c==5) return 3;
    return 0;
}

int main(){
    scanf("%s",s+1);
    n=strlen(s+1);
    int y=0;
    for (int i=1;i<=n;){  //字符串->表达式
        char c=s[i];
        int t=op(c);
        if (t!=0){
            if (t==2 && !y){
                y=1;
                i++;
                int tmp=0;
                while (i<=n && op(s[i])==0){
                    tmp=tmp*10+s[i]-'0';
                    i++;
                }
                a[++cnt]={0,-tmp};
            }else{
                a[++cnt]={1,t};
                i++;
                y=0;
                if (t==-2) y=1;
            }
        }else{
            int tmp=0;
            y=1;
            while (i<=n && op(s[i])==0){
                tmp=tmp*10+s[i]-'0';
                i++;
            }
            a[++cnt]={0,tmp};
        }
    }
    n=0;y=0;
    for (int i=1;i<=cnt;++i){  //中缀->后缀
        if (!a[i].op) a[++n]=a[i];
        else{
            if (a[i].val==-1){
                y++;  //左括号计数
                st.push(a[i]);
            }else if (a[i].val==-2){
                if (y==0) continue;  //处理多余的右括号
                while (!st.empty() && st.top().val!=-1){
                    a[++n]=st.top();
                    st.pop();
                }
                st.pop();
                y--;
            }else{
                while (!st.empty() && lv(st.top().val)>=lv(a[i].val)){
                    a[++n]=st.top();
                    st.pop();
                }
                st.push(a[i]);
            }
        }
    }
    while (!st.empty()){
        if (st.top().val!=-1) a[++n]=st.top(); //处理多余的左括号
        st.pop();
    }
    for (int i=1;i<=n;++i){  //后缀计算
        if (!a[i].op){
            st.push(a[i]);
        }else{
            int x,y,c;
            y=st.top().val;st.pop();  //注意xy的先后顺序
            x=st.top().val;st.pop();
            if (a[i].val==1) c=x+y;
            if (a[i].val==2) c=x-y;
            if (a[i].val==3) c=x*y;
            if (a[i].val==4) c=x/y;
            if (a[i].val==5) c=pow(x,y);
            st.push({0,c});
        }
    }
    printf("%d\n",st.top().val);
    return 0;
}

前缀表达式求值

前缀表达式求值很简单，按照后缀表达式的处理办法倒着扫描即可

本作品采用知识共享署名-非商业性使用-相同方式共享 3.0 未本地化版本许可协议进行许可。
本文链接：https://hs-blog.axell.top/archives/101/