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

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

首先将中缀表达式转换成前缀表达式
前缀表达式中，操作符在前
例如：1+2*(5-3)+4
后缀表达式：++1*2-534

一、转换思路

转换思路为将输入的中缀表达式字符串从右往左扫描(字符前后加#号)，遇到数字直接输出，遇到操作符比较优先级。
栈顶优先级低，入栈；
栈顶优先级高，出栈并且输出；
优先级相等(即左右括号)，出栈(不输出)；
当扫描的字符为#并且栈顶字符为#时，此时将输出的字符序列反转即为前缀表达式。
注意：优先级顺序表与求中缀表达式和后缀表达式的优先级顺序表不同

二、前缀表达式求值过程

将转换成的前缀表达式的字符串从右往左扫描，扫描到数字时进栈，扫描到字符从栈中出两个数字，然后与扫描到的字符之间进行运算， <运算时注意：先出栈的做运算符的前操作数，后出栈的做后操作数> 这与后缀、前缀表达式求值恰好相反。当全部扫描完后，栈顶的元素即为运算结果。

前缀表达式求值优先级：

该优先级表与中缀和后缀表达式求值区别主要有：相同操作符(+ - * /)栈顶优先级低；预比较运算符 ） 优先级最高，（ 最低；栈顶 )、 预比较 ( 相等

三、代码展示

#include <iostream>
#include <string>
#include <algorithm>
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){
    //将字符串反转 然后在字符串最后加一个#标志符
    reverse(s.begin(),s.end());
    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;
    reverse(s1.begin(),s1.end());
    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]=='-'){
            a=pop(OPND);
            b=pop(OPND);
            theta=s1[i];
            push(OPND,operate(a,theta,b));

        }
    }
    return getTop(OPND);
}
int main(){
push(OPTR,'#');
cout<<"请输入中缀表达式:";
cin>>s;
suffix(s);
 cout<<"前缀表达式："; 
 //反转字符串
 reverse(s1.begin(),s1.end());
  cout<<s1<<endl;
  cout<<"表达式结果：";
  cout<<calculation(s1)<<endl;
    return 0;
}

四、结果展示

五、局限

局限输入、中间或者结果值只能在0-9范围内，因为ASCII码转数字的问题只能是0-9