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

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

话题1：中缀表达式To后缀表达式

中缀表达式转后缀表达式，首先我们要准备两个字符数组，一个是用来存我们输入的中缀表达式，另一个是用来存我们处理得到的后缀表达式，其次，我们还要准备一个操作符栈，来存储那些还不能确定拼接时机的那些操作符。这里的拼接指的是将操作符拼接到后缀表达式中。

转化的具体原理：

在此我们先给出操作符优先级，方便后续阐述:(前提:我们的表达式是四则运算)

')' > '*' = '/' > '+' = '-' > '('

1. 遍历整个中缀表达式数组；

2. 如若当前位置字符在'0'~'9'之间或者它是小数点，直接把这个字符插入后缀表达式数组；

3. 如果当前字符是空格，则只需将遍历的循环控制变量+1，其他不变；

4. 如果当前字符是：

   • '(' : 直接入栈，因为左括号的优先级最低

   • ')' : 将操作符栈中的操作符以此弹出并拼接到后缀表达式上，直到遇到与其配对的'('. 注意：这里左右括号不加入后缀表达式！！

   • +、-、*、/：这时我们要比较当前字符表示的操作符和操作符栈栈顶操作符的优先级大小，此处又要分两种情况处理：

     1. 操作符栈栈顶操作符优先级不小于当前遍历位置操作符的优先级的话，那么直接弹栈，并将弹出的操作符拼接至后缀表达式中，重复这个操作直至栈顶优先级小于当前遍历位置操作符优先级

     2. 操作符栈栈顶操作符优先级小于当前遍历位置操作符的优先级的话，那么直接将当前位置操作符压入操作符栈中。

5. 出口处理：如果整个中缀表达式遍历完了，操作符栈中还有元素，那么直接将栈中元素依次弹出并拼接至后缀表达式后。

    

   至此，我们将成功将一个中缀表达式转化为一个后缀表达式了......

   接下来我们要对后缀表达式按一定的计算方法进行求值

    

    

话题2 后缀表达式求值

我们要事先准备一个操作数栈，暂存部分操作数。

后缀表达式求值原理：遍历整个后缀表达式

1. 如若当前位置字符是满足>='0'&&<='9',那么交给一个求值函数(下面代码中又详解)，并将返回值压入操作数栈中

2. 如若当前位置字符是空格，什么都不用动，只需将循环控制变量+1

3. 如果当前位置字符是操作符，那么操作数栈弹栈(连续两次)，将弹出的两个操作数进行操作符指示相应的计算，并将计算结果压入操作数栈中

4. 出口处理，整个后缀表达式遍历结束：此时操作数栈栈顶元素的值即为整个表达式的值，也即我们最初的中缀表达式的值。

接下来是上述两个Topic的代码展示：(能力没到，代码略显冗长^_^望批评斧正！)

 #include<cstdio>
 #include<cstring>
 #include<iostream>
 #include<algorithm>
 const int N = 100;
 char zz[N];//存储中缀表达式
 char hz[N];//存储后缀表达式
 ​
 char opst[N];//操作符栈，用来将中缀表达式转化为后缀表达式 
 double numst[N];//操作数栈，用来求后缀表达式的值 
 ​
 using namespace std;
 bool is_op(char c){
     //判断是否为操作符函数。
     switch(c){
         case '+':
         case '-':
         case '*':
         case '/':
             return true;
         default:
             return false;
     }
 }
 int op(char c) {//定义优先级 
     switch(c){
         case '+':
         case '-':
             return 0;
         case '*':
         case '/':
             return 1;
         case '(':
             return -1;
         default:
             return -1;
     }
 }
 ​
 double getsum(int *i){
     //后缀表达式求数值的函数。这里注意：地址传递！！
     double sum = 0.0;int k=0;
     while(hz[*i]>='0' && hz[*i]<='9'){
         sum = sum * 10 + hz[*i] - '0';
         (*i)++; 
     }
     if(hz[*i]=='.'){
         (*i)++;
         while(hz[*i]>='0' && hz[*i]<='9'){
             (*i)++;
             k++;
             sum = sum * 10 + hz[*i] - '0'; 
         }
     }
     
     while(k!=0){
         k--;
         sum = sum/10;
         //把小数处理时乘上的若干个10再除去
     }
     
     return sum;
 }
 int main(){
     gets(zz);//输入中缀表达式 (输入‘#’表结束） 
     
     //中缀表达式转后缀表达式
     //操作数栈顶大于当前优先级，弹栈 
     int i=0,j=0,top=-1;
     while(zz[i]!='#'){
         if(zz[i]<='9'&&zz[i]>='0'||zz[i]=='.'){
             hz[j++] = zz[i++];
         }else if(zz[i]==' '){
             hz[j++] = ' ';
             i++;
         }else if(zz[i]=='('){
             opst[++top] = '(';
             i++;
         }else if(zz[i]==')'){
             while(opst[top]!='('){
                 hz[j++] = opst[top--];
             }
             top--;
             i++;
         }else if(is_op(zz[i])){
             hz[j++] = ' ';
             while(op(opst[top]) >= op(zz[i])){
                 hz[j++] = opst[top--];
     } 
opst[++top] = zz[i]; 
i++; 
    } 
    } 
while(top!=-1){ 
hz[j++] = opst[top--]; 
    } 
hz[j++] = '#';  
      
puts(hz); 
//上述操作已然得到后缀表达式，就剩下求值了 
//现在所有有效数据都在后缀表达式中--即hz[] 数组中 
//下面进行的时后缀表达式求值 
i=0,top=-1; 
double x1,x2; 
while(hz[i]!='#'){ 
if(hz[i]>='0' && hz[i]<='9'){ 
numst[++top] = getsum(&i);//地址传递为的是一边计算的过程中一边改变i的值，  
    }else if(hz[i] == ' '){ 
i++; 
    }else if(hz[i] == '+'){ 
x1 = numst[top--]; 
x2 = numst[top--]; 
numst[++top] = x1+x2; 
i++; 
    }else if(hz[i] == '-'){ 
x1 = numst[top--]; 
x2 = numst[top--]; 
numst[++top] = x2-x1; 
i++; 
    }else if(hz[i] == '*'){ 
x1 = numst[top--]; 
x2 = numst[top--]; 
numst[++top] = x1*x2; 
i++; 
    }else if(hz[i] == '/'){ 
x1 = numst[top--]; 
x2 = numst[top--]; 
numst[++top] = x2/x1; 
i++; 
    } 
    } 
     
//测试数据 
//(8-7)*4+2-3*8#  
// 3+8/(4+2)-7+4*2#  
cout<<numst[top]<<endl; 
return 0; 
} 

运行展示图：