P1175 表达式的转换 题解

· · 题解

艾玛表达式树高斯我了

P1175 表达式的转换

题目描述

平常我们书写的表达式称为中缀表达式，因为它将运算符放在两个操作数中间，许多情况下为了确定运算顺序，括号是不可少的，而后缀表达式就不必用括号了。

后缀标记法：书写表达式时采用运算紧跟在两个操作数之后，从而实现了无括号处理和优先级处理，使计算机的处理规则简化为：从左到右顺序完成计算，并用结果取而代之。

例如：8-(3+2*6)/5+4 可以写为：8 3 2 6 * + 5 / - 4 +

其计算步骤为：

8 3 2 6 * + 5 / - 4 +
8 3 12 + 5 / - 4 +
8 15 5 / - 4 +
8 3 - 4 +
5 4 +
9

编写一个程序，完成这个转换，要求输出的每一个数据间都留一个空格。

题目大意

给你一个表达式，让你写成后缀形式，然后输出解的过程。

（这题很离谱，前方高能！）

题目解法

表达式转后缀化简，表达式树裸题了

建树

最烦的一步

先找根：

有加减找最后一个加减，

有乘除找最后一个乘除，

否则找第一个幂（找最后一个 Sub1 过不掉）

注意括号内要看成一个整体（不然递归到后面会出错） 但是！！

如果整个柿子是形如 (xxxxx) 型要先把外括号干掉！ 但是！！

一定要是对应！！否则 (2+3) \times (4+5) 卡死你！

找到根就好做了，直接分开两边继续递归就行了。 最后我们要知道：

计算+输出答案

从根节点开始往下搜，搜出可以算的节点就算（一定在叶子附近），计算完了对树后序遍历输出就好了。

（注：你可能还要写一个武则天计算器）

详情请见注释

代码

嗨害嗨 

#include<bits/stdc++.h>
#define N 114514
using namespace std;
string op;
char ch[N];int num[N],lf[N],rf[N],cnt=0;// ch是运算符，num是值，cnt是节点个数，lf,rf左右儿子
void build(int l,int r){//建表达式树
    if(l==r){
        num[++cnt]=op[l]-'0';
        ch[cnt]=' ';
        return;
    }//叶子结点存好
    if(op[l]=='('){//判断是否为(xxxxx)型
        int go=1;
        for(int i=l+1;i<=r;++i){
            if(op[i]=='(') ++go;
            else if(op[i]==')') --go;
            if(go==0){//找到对应的')'了
                if(i==r) ++l,--r;//判断是否为首尾
                break;
            }
        }
    }
    int p,typo=5;//p为根的坐标
    //typo:+1-1*2/2^3
    for(int i=r;i>=l;--i){
        if(op[i]==')'){//跳过括号
            int go=1,j;
            for(j=i-1;j>=l;--j){
                if(op[j]==')') ++go;
                else if(op[j]=='(') --go;
                if(go==0) break;
            }
            i=j;continue;
        }else if(op[i]<='9'&&op[i]>='0') continue;//跳过数字
        else{//对符号分类讨论
            if((op[i]=='+'||op[i]=='-')&&typo>1) p=i,typo=1;//有加减就加减
            else if((op[i]=='*'||op[i]=='/')&&typo>2) p=i,typo=2;//有乘除就乘除
            else if(op[i]=='^'&&typo>3) p=i,typo=4;//找幂
        }
    }
    int x=++cnt;
    ch[x]=op[p];//更新自己
    lf[x]=cnt+1;
    build(l,p-1);//向左子树递归
    rf[x]=cnt+1;
    build(p+1,r);//向右子树递归
}
int calc(int a,int b,char gk){
    switch(gk){
        case '+':return a+b;
        case '-':return a-b;
        case '*':return a*b;
        case '/':return a/b;
        case '^':return pow(a,b);
    }
}//武则天计算器
void print(int u){//后序遍历输出
    if(ch[u]==' '){
        cout<<num[u]<<" ";
        return;
    }
    print(lf[u]);print(rf[u]);
    cout<<ch[u]<<" ";
}
void dfs(int x){//递归计算
    if(ch[x]==' ') return;
    dfs(lf[x]);dfs(rf[x]);//算左右子树
    num[x]=calc(num[lf[x]],num[rf[x]],ch[x]);//计算本节点
    ch[x]=' ';//复位叶子
    print(1);cout<<endl;//输出运算过程
}
int main(){
    cin>>op;
    build(0,op.size()-1);
    print(1);cout<<endl;
    dfs(1);
    return 0;
}

珍爱账号，远离抄袭！

（记得点赞