题解 P1175 【表达式的转换】

璀璨星辰 · 2018-02-28 13:26:34 · 题解

直接放代码和注释了

#include<bits/stdc++.h>
#define For(i,l,r) for(int i=(l);i<=(r);i++)
using namespace std;   //+  -  *  /  ( )  ^
const int prior[7][7]={{ 1, 1,-1,-1,-1,1,-1},         
/*栈顶运算vs当前运算*/ { 1, 1,-1,-1,-1,1,-1},       
/*栈顶运算优先算，置1*/{ 1, 1, 1, 1,-1,1,-1},
/*当前运算先算，置-1*/ { 1, 1, 1, 1,-1,1,-1},
/*对括号特殊处理，置0*/{-1,-1,-1,-1,-1,0,-1},        //左边为左括号，则右边什么运算都要先算，除了右括号 
                       { 0, 0, 0, 0, 0,0, 0},           //这一行其实没有意义可以随便赋初值，因为左括号不会出现在栈顶 
                       { 1, 1, 1, 1,-1,1, 1}};      
char strh[2000]={0},strz[2000]={0};         //后缀表达式字符串，中缀表达式字符串 
char opst[10000],top=0;                     //运算符栈 
int numst[10000],t=0;
int f(char op){     //将运算符对应到0-6的标号 
    switch(op){
        case '+': return 0;
        case '-': return 1;
        case '*': return 2;
        case '/': return 3;
        case '(': return 4;
        case ')': return 5;
        case '^': return 6; 
    }
}

void convert(char strz[],char strh[]){
    int len=strlen(strz);
    int j=0;
    opst[++top]='('; //在最外层添加左括号 

    //以下部分，opst[top]是栈顶的上一个运算符，strz[i]是当前扫描到的运算符 

    For(i,0,len-1){             
        if (isdigit(strz[i])) strh[j++]=strz[i];        //如果是操作数，直接输出到strh中 
        else {
            while (prior[f(opst[top])][f(strz[i])]>0)   //将所有优先于strz[i]的opst[top]都弹出 
                strh[j++]=opst[top--];
            if (prior[f(opst[top])][f(strz[i])]==0)     //如果str[i]是右括号，将栈顶的左括号弹出 
                top--;
            else
                opst[++top]=strz[i];                    //如果str[i]不是右括号，将strz[i]压入栈
        }
    }
}

void print(char s[]){//给后缀表达式的剩余部分加上空格输出 
    int len=strlen(s);
    For(i,0,len-1){
        printf("%c ",s[i]); 
    }
    printf("\n");               
}

void cal(char strh[]){      //后缀表达式的计算 
    int len=strlen(strh);
    print(strh);            //输出后缀表达式本身 
    For(i,0,len-1)          //扫描后缀表达式 
        if (isdigit(strh[i])) numst[++t]=strh[i]-'0';       //数字字符就入操作数栈 
        else {
            t--;                                            //否则根据strh[i]运算符对栈顶的两个元素进行计算 
            switch(strh[i]){
                case '+':numst[t]=numst[t]+numst[t+1];break;
                case '-':numst[t]=numst[t]-numst[t+1];break;
                case '*':numst[t]=numst[t]*numst[t+1];break;
                case '/':numst[t]=numst[t]/numst[t+1];break;
                case '^':numst[t]=pow(numst[t],numst[t+1]);break;
            }
            For(j,1,t) printf("%d ",numst[j]);              //输出计算完这一步的后缀表达式中间过程 
            print(strh+i+1);                                //分两段输出，前面一段对应操作数栈，后面一段对应未扫描的strh 
        }
}

int main(){
    gets(strz);
    int len=strlen(strz);
    strz[len]=')';
    strz[len+1]='\0';
    //在最外层添加右括号 
    convert(strz,strh);
    cal(strh);
    return 0;
}