[数据结构与算法]【数据结构】中缀表达式转后缀表达式求值

中缀表达式转后缀表达式求值

首先需要将输入的中缀表达式转换成后缀表达式。
后缀表达式中，操作符在后
例如：1+2*(5-3)+4
后缀表达式：1253-*+4+

1、中缀表达式转换成后缀表达式方法：

首先，需要定义一个操作符栈并且知道各运算符优先级，然后从左往右一次扫描字符(字符前后加#号)，遇到数字直接输出，遇到操作符比较优先级。
栈顶优先级低，入栈；
栈顶优先级高，出栈并且输出；
优先级相等(即左右括号)，出栈(不输出)；
当扫描的字符为#并且栈顶字符为#时，此时输出的字符序列即为后缀表达式

2、后缀表达式求值过程

转换成后缀表达式后，即可利用后缀表达式进行求值，后缀表达式求值时，只需定义一个操作数栈，当从左往右扫描字符串时，扫描到数字时进栈，扫描到字符从栈中出两个数字，然后与扫描到的字符之间进行运算，当全部扫描完之后，栈顶的数字即为求值结果

3、代码实现

#include <iostream>
#include <string>
using namespace std;

string s;  //中缀表达式字符串
string s1="\0"; //后缀表达式字符串
char OPTR[100]; //操作符栈
char OPND[100]; //操作数栈
int topN=-1,topT=-1;

//栈的基本操作
void push(char *OPTR,char ch){
        OPTR[++topT]=ch;
}
void push(int *OPND,int val){
        OPND[++topN]=val;
}
char pop(char *OPTR){
        return OPTR[topT--];
}
int pop(int *OPND){
        return OPND[topN--];
}
int getTop(int *OPND){
    return OPND[topN];
}
char getTop(char *OPTR){
    return OPTR[topT];
}

//定义一个二位字符数组存放优先级表
char arr[7][7]= {'>','>','<','<','<','>','>',
                 '>','>','<','<','<','>','>',
                 '>','>','>','>','<','>','>',
                 '>','>','>','>','<','>','>',
                 '<','<','<','<','<','=','\0',
                 '>','>','>','>','\0','>','>',
                 '<','<','<','<','<','\0','='
                };
//定义字符表
int opCH(char ch){
    int i;
        switch(ch){
    case '+':{
        i=0;
        break;
    }
    case '-':{
        i=1;
        break;
    }
    case '*':{
        i=2;
        break;
    }
    case '/':{
        i=3;
        break;
    }
    case '(':{
        i=4;
        break;
    }
    case ')':{
        i=5;
        break;
    }
    case '#':{
        i=6;
        break;
    }
 }
 return i;
}
//比较运算符的优先级
char percede(char ch1,char ch2){
    int i,j;
    i=opCH(ch1);
    j=opCH(ch2);
    return arr[i][j];
}

int operate(int a,char theta,int b){
    switch(theta){
    case '+':{
            return a+b;
    }
    case '-':{
            return a-b;
    }
    case '*':{
            return a*b;
    }
    case '/':{
            return a/b;
    }
 }
 return 0;

}
void suffix(string s){
    for(int i=0;s[i]!='#'||getTop(OPTR)!='#';i++){
        if(s[i]>48&&s[i]<58){
            s1+=s[i];  //如果是数字的话放入新字符串
        }else if(s[i]=='*'||s[i]=='/'||s[i]=='+'||s[i]=='-'||
                 s[i]=='('||s[i]==')'||s[i]=='#'){
            switch(percede(getTop(OPTR),s[i])){
        case '>':{
                s1+=pop(OPTR);//栈顶优先级高的话放入新字符串
                i--;
                break;
        }
        case '<':{
                push(OPTR,s[i]);
                break;
        }
        case '=':{
                if(s[i]==')'){
                    pop(OPTR);
                }
        }
      }
    }
 }
}

int calculation(string s1){
    int a,b,c;
    char theta;
    for(int i=0;s1[i]!='\0';i++){
        if(s1[i]>48&&s1[i]<58){
            c=s1[i]-48;
            push(OPND,c);//扫描到操作数压栈
        }else if(s1[i]=='*'||s1[i]=='/'||s1[i]=='+'||s1[i]=='-'){
            b=pop(OPND);//扫描到操作符就 从栈中弹出两个操作数进行运算
            a=pop(OPND);
            theta=s1[i];
            push(OPND,operate(a,theta,b));

        }
    }
    return getTop(OPND);
}
int main(){
push(OPTR,'#');
cout<<"请输入中缀表达式，以#符号结束：";
cin>>s;
suffix(s);
 cout<<"后缀表达式：";
  cout<<s1<<endl;
  cout<<"表达式结果：";
  cout<<calculation(s1)<<endl;
    return 0;
}

代码实现与中缀表达式求值类似

中缀表达式求值：

https://blog.csdn.net/weixin_51799151/article/details/120643674