题解 P1175 【表达式的转换】

· · 题解

（发现表达式计算好题一道，然而为什么来做这题的人不怎么多？）

作为中缀表达式计算新学选手，简单解释一番。

首先要学会中缀表达式转后缀：（方式上只写一个我自己的理解）

1.遇到操作数直接输出

2.遇到运算符号——利用建立的符号栈，栈内总原则为高级运算压在低级运算之上

3.遇到左括号，左括号入栈，左括号虽然在栈外的优先级（运算优先级）最高，但在栈内的优先级最低

4.遇到加、减、乘、除、乘方，按照正常的运算优先级处理

5.遇到右括号，持续出栈操作，不停打印符号直至遇到左括号（左括号只出栈不输出）

6.如果要入栈的符号不为右括号，则从栈顶开始，将运算优先级高于或等于待入栈符号的所有符号逐一出栈输出，直到遇到栈内优先级低于入栈符号的符号为止

7.读入结束，将符号栈内所有剩余符号出栈输出

（只要遵循这几个条件就可以将它们翻译成代码模拟了）

几个注意点：

1.括号绝对不输出，右括号没必要入栈

2.这题要注意打印时空格的处理

3.其实C党可以使用sprintf来简化输出操作（数字和空格都可以直接打到一个字符串里，然后使用puts就得到了第一行结果），然而我忘记用了，完全依靠大力分离字符

然后就是对于一个后缀表达式的计算操作：

1.每次只找到第一个运算符号，然后往前查到两个运算数

2.对两个运算数进行与运算符号相同的运算，将这一对运算数和它们的运算符去掉，把运算结果放回原处。

3.每次都输出一遍

4.注意负号和减号的不同——负号不是运算符，后面紧跟着一个数字，而减号后紧跟着一个空格。

虽然没有高精度的要求，此题编程量仍然较大，细节问题超多，需要耐心，务必勤于单步调试。

写1小时调3小时也是很可能的，这一点永远只会字符数组模拟字符串（直接导致代码量浩大）的本蒟蒻深有体会。

贴出我那写得根本不可读的代码：


#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<cmath>
#include<cctype>
#include<algorithm>
#include<string>
#include<vector>
#define hk 100010
using namespace std;//写完了才发现好像把数组开得太大了= =（但我第一次爆炸是因为数组开太小了）
int prio[hk],i,j,num1,num2,st,curr,m[hk],ope,top,len,stack[hk];char s[hk],anss[hk],ans[hk];bool bo;
int power(int a,int b){//计算a^b的准确值，快速幂，没有高精度也就不虚了
    if(!b)return 1;int x=power(a,b>>1);x*=x;
    if(b&1)return x*a;else return x;
}
int main(){//开始螺杆（这是我的第四发程序，终于AC了）
    prio['+']=prio['-']=1;prio['*']=prio['/']=2;prio['^']=3;prio['(']=4;fgets(s,hk,stdin);s[strlen(s)-1]=0;//规定运算优先级；fgets();会多出一个回车，记得把它去掉
    i=0;while(i<strlen(s)){
        if(isdigit(s[i])){while(isdigit(s[i])&&i<strlen(s)){anss[len++]=s[i];i++;}anss[len++]=32;}//操作数字只需要复制一遍就好辣
        if(i<strlen(s)){
            if(s[i]==')'){
                while(stack[top]-'('&&top){anss[len++]=stack[top];anss[len++]=32;top--;}
                top--;//碰到右括号就不停出栈知道遇到左括号（其实只要表达式正确就不至于栈空）
            }else if(prio[s[i]]>prio[stack[top]]||stack[top]=='(')stack[++top]=s[i];else{//else前面是强行入栈
            while(prio[s[i]]<=prio[stack[top]]&&stack[top]-'('&&top){anss[len++]=stack[top];anss[len++]=32;top--;}stack[++top]=s[i];}i++;//持续出栈
        }
    }while(top){anss[len++]=stack[top];anss[len++]=32;top--;}puts(anss);//从主程序开始到这里都是在中缀转后缀
    while((isdigit(anss[i])||anss[i]==32||anss[i]=='-'&&anss[i+1]-32)&&i<strlen(anss))i++;if(!anss[i]){puts(anss);return 0;}//如果没有运算符号处理，说明输入的就是一个数字，直接退出，请千万注意这个特判
    while(1){
        i=0;while((isdigit(anss[i])||anss[i]==32||anss[i]=='-'&&anss[i+1]-32)&&i<strlen(anss))i++;if(anss[i])ope=i;else break;//如果没有运算符号处理，就不玩了
        i-=2;while(isdigit(anss[i])||anss[i]=='-'&&anss[i+1]-32)i--;i--;while(isdigit(anss[i])||anss[i]=='-'&&anss[i+1]-32)i--;i++;//强行查找操作数的起始点
        for(j=0;j<i;j++)ans[j]=anss[j];//前面半段表达式直接复制
        num1=0;bo=0;if(anss[i]=='-'){i++;bo=1;}while(isdigit(anss[i])){num1=num1*10+anss[i]-48;i++;}if(bo)num1=-num1;i++;
        num2=0;bo=0;if(anss[i]=='-'){i++;bo=1;}while(isdigit(anss[i])){num2=num2*10+anss[i]-48;i++;}if(bo)num2=-num2;switch(anss[ope]){//switch前把两个操作数分离出来，switch里面做的是运算操作
            case'+':st=num1+num2;break;case'-':st=num1-num2;break;case'*':st=num1*num2;break;case'/':st=num1/num2;break;
            case'^':st=power(num1,num2);break;//不要忘记这题要求计算乘方（我的第三发爆炸原因）
        }memset(m,0,sizeof(m));curr=st;if(st<0){ans[j++]='-';st=-st;}while(st){
            m[++m[0]]=st%10;st/=10;//强行分离数位方便逐字符打印
        }if(!m[0])ans[j++]=48;else for(;m[0];m[0]--)ans[j++]=m[m[0]]+48;//请特别小心0的处理（我的第二发爆炸原因）
        for(i=ope+1;i<strlen(anss);i++)ans[j++]=anss[i];ans[j++]=0;//复制剩余部分
        if(ope+2==strlen(anss)){printf("%d",curr);break;}else puts(ans);for(i=0;i<strlen(ans);i++)anss[i]=ans[i];anss[i]=0;//中间字符串的迭代
    }return 0;
}

版权归jiangyougogogo (i.e. J.S.S.Y.)所有，复制请注明出处，盗版必究。

如果有勘误恳请及时指正。