顺序栈的应用五：表达式求值

表达式求值

这里介绍一种简单直观的“算符优先法”。

要对一个表达式求值，首先要能够正确解释表达式。
例如，要求对下面的算术表达式求值：
4+2*3-10/5

首先要了解算术四则运算的规则。即：
(1)先乘除，后加减
(2)从左算到右
(3)先括号内，后括号外。

由此，这个算术表达式的计算顺序应为：
4 + 2 * 3 - 10 / 5 = 4 + 6 - 10 / 5 = 10 - 10 / 5 = 10 - 2 =8

算符优先法就是根据这个运算关系的规定来实现对表达式的编译或解释执行的。
任何一个表达式都是由操作数(operand)、运算符(operator)和界限符(delimiter)组成的。
一般的，操作数既可以是常数也可以是被说明为变量或常量的标识符；
运算符可以分为算术运算符、关系运算符和逻辑运算符3类；
基本界限符有左右括号和表达式结束符等。

我们把运算符和界限符统称为算符，他们构成的集合命名为OP。根据上述3条运算规则，在运算的每一步中，任意两个相继出现的算符a和b之间的优先关系至多是下面三种关系之一：
a<b：a的优先级低于b
a=b：a的优先级等于b
a>b：a的优先级大于b

下表给出了部分a、b运算符之间的优先级关系（列为a运算符，行为b运算符）：

	+	-	*	/	%	(	)
+	>	>	<	<	<	<	>
-	>	>	<	<	<	<	>
*	>	>	>	>	>	<	>
/	>	>	>	>	>	<	>
%	>	>	>	>	>	<	>
(	<	<	<	<	<	<	=
)	>	>	>	>	>	N	N

表达式中的‘=’表示当左右括号相遇时，括号内的运算完成，此时要把左右括号从表达式中及时脱离。
表达式中的'N'表示这种状态如果出现了，则表达式格式有误，一定是左右括号不匹配。

在代码中，我给出了上述7种运算符

char opetr_char[7]={'+','-','*','/','%','(',')'};

首先是要判断一个字符属不属于运算符，

int isOpetrChar(char ch){
    int i;
    for(i=0;i<7;i++){
        if(ch ==  opetr_char[i]) return i;
    }
    return -1;
}

上表的优先级用一个char型的二维数组直观表示：

char opetr_priority[7][7]={
    {'>','>','<','<','<','<','>'},
    {'>','>','<','<','<','<','>'},
    {'>','>','>','>','>','<','>'},
    {'>','>','>','>','>','<','>'},
    {'>','>','>','>','>','<','>'},
    {'<','<','<','<','<','<','='},
    {'>','>','>','>','>','N','N'}
};

那么，比较两个运算符的优先级可以简单得出：

char getOpetrPrior(char a,char b){
    int i = isOpetrChar(a);
    int j = isOpetrChar(b);
    return opetr_priority[i][j];
}

实现算符优先算法，可以使用两个栈，一个optr_stack，用于存放运算符，一个opnd_stack，用于存放操作数。
算法的核心思想是，依次读入表达式中每个字符，若是操作数则进opnd_stack，若是运算符则与optr_stack的栈顶操作符比较优先权后作相应操作，直至整个表达式求值完毕。

EvaluateExpression.c利用了前面的C封装的顺序栈对象 用线性表表示的顺序栈

实现了输入表达式，显示每一步的计算过程，并输出最终结果的功能。
且支持表达式格式检测，支持多重括号结构、负数运算（‘-’号既可能为减号，也可能为负号）。

github源码

EvaluateExpression.c文件

#include <stdio.h>
#include <malloc.h>
#include "LinearListStack.h"

char opetr_char[7]={'+','-','*','/','%','(',')'};

//operational character priority (a,b),operational character b after a.
//   b: +  -  *  /  %  (  )
// a:
// +    >  >  <  <  <  <  >
// -    >  >  <  <  <  <  >
// *    >  >  >  >  >  <  >
// /    >  >  >  >  >  <  >
// %    >  >  >  >  >  <  >
// (    <  <  <  <  <  <  =
// )    >  >  >  >  >  N  N

char opetr_priority[7][7]={
    {'>','>','<','<','<','<','>'},
    {'>','>','<','<','<','<','>'},
    {'>','>','>','>','>','<','>'},
    {'>','>','>','>','>','<','>'},
    {'>','>','>','>','>','<','>'},
    {'<','<','<','<','<','<','='},
    {'>','>','>','>','>','N','N'}
};

int isOpetrChar(char ch){
    int i;
    for(i=0;i<7;i++){
        if(ch ==  opetr_char[i]) return i;
    }
    return -1;
}

char getOpetrPrior(char a,char b){
    int i = isOpetrChar(a);
    int j = isOpetrChar(b);
    return opetr_priority[i][j];
}

double my_pow(double a,int b){
    int s = 0,i;
    double r = 1;
    if(b == 0) return 1;
    if(b<0){
        b*=-1;
        s = 1;
    }
    for(i = 0; i < b; i++){
        r *= a;
    }
    if(s) r = 1/r;
    return r;
}

int getOpndNumFromStack(LinearListStack *opnd_stack){
    int num = 0,i = 0;
    char elem;
    if(opnd_stack->length(opnd_stack)){
        opnd_stack->pop(opnd_stack,&elem);
        if(elem == ' '){
            while(elem == ' '){
                if(opnd_stack->length(opnd_stack) == 0) break;//确保不会pop空栈
                opnd_stack->pop(opnd_stack,&elem);
            }
        }
        if(elem != ' '){ //两个判断必须分开来写
            while(elem != ' ' && elem != '-'){
                num += my_pow(10,i)*(elem - 0x30);
                if(opnd_stack->length(opnd_stack) == 0) break; //确保不会pop空栈
                opnd_stack->pop(opnd_stack,&elem);
                i++;
            }
            if(elem == '-'){ //如果是负号
                num = -num;
            }else if(elem == ' '){  //将移出的空格间隔符再补进去
                opnd_stack->push(opnd_stack,&elem);
            }
        }
    }
    return num;
}

int operate(int number_a,char opetr_char,int number_b){
    int result = 0;
    switch(opetr_char){
        case '+':
            result = number_a + number_b;
            break;
        case '-':
            result = number_a - number_b;
            break;
        case '*':
            result = number_a * number_b;
            break;
        case '/':
            result = number_a / number_b;
            break;
        case '%':
            result = number_a % number_b;
            break;
        default:
            result = number_b;
            break;
    }
    return result;
}

void pushResultToStack(LinearListStack *opnd_stack, int result){
    char elem[10],n_elem;
    int i = 0,index = 0;
    if(result < 0){
        result = - result;
        n_elem = '-';
        opnd_stack->push(opnd_stack,&n_elem);
    }else if(result == 0){
        n_elem = '0';
        opnd_stack->push(opnd_stack,&n_elem);
    }
    while(result > 0){
        elem[index] = (result % 10) + 0x30;
        result /= 10;
        index++;
    }
    for(i=index;i>0;i--){
        opnd_stack->push(opnd_stack,&elem[i-1]);
    }
}

LinearListStack *evaluateExpression(char *str){
    char elem,opetr_prior,opetr_char;
    int cal_result = 0,number_a,number_b;
    int num_before_flag = 0;
    LinearListStack *optr_stack = InitLinearListStack(); //运算符栈
    LinearListStack *opnd_stack = InitLinearListStack(); //操作数栈
    while(*str != '\0'){
        if(isOpetrChar(*str) != -1){
            if(optr_stack->length(optr_stack)){
                optr_stack->getTop(optr_stack,&elem);
                opetr_prior = getOpetrPrior(elem,*str);
                switch(opetr_prior){
                    case '<': //栈顶运算符优先级低
                        if(num_before_flag == 0){ //前一个入栈的是符号
                            if(*str == '-'){ //此时'-'号表示为负号
                                opnd_stack->push(opnd_stack,str);//'-'号加入操作数栈
                                num_before_flag = 1; //加入的是数字
                            }else if(elem == '(' || *str == '('){ //多个括号与操作符相邻的情况
                                optr_stack->push(optr_stack,str);  
                                elem = ' '; //数字字符加入空格间隔符
                                opnd_stack->push(opnd_stack,&elem);
                                num_before_flag = 0;//加入运算符
                            }else{
                                printf("Expression format error!");
                                break;
                            }
                        }else{ //前面有数字入栈
                            optr_stack->push(optr_stack,str);  
                            elem = ' '; //数字字符加入空格间隔符
                            opnd_stack->push(opnd_stack,&elem);
                            num_before_flag = 0;//加入运算符
                        }
                        break;
                    case '=':
                        optr_stack->pop(optr_stack,&elem);//脱括号
                        num_before_flag = 1; //脱括号等效为加入的是数字
                        break;
                    case '>': //栈顶运算符优先级高
                        if(num_before_flag == 0){ //前一个入栈的是符号
                            if(*str == '-'){ //此时'-'号表示为负号
                                opnd_stack->push(opnd_stack,str);//'-'号加入操作数栈
                                num_before_flag = 1; //加入的是数字
                            }else{
                                printf("Expression format error!");
                                break;
                            }
                        }else{ //前一个入栈的是数字
                            optr_stack->pop(optr_stack,&opetr_char);//取运算符
                            number_b = getOpndNumFromStack(opnd_stack);
                            number_a = getOpndNumFromStack(opnd_stack);
                            cal_result = operate(number_a,opetr_char,number_b);
                            printf("%d",number_a);
                            printf(" %c ",opetr_char);
                            printf("%d = ",number_b);
                            printf("%d\n",cal_result);
                            pushResultToStack(opnd_stack, cal_result);
                            num_before_flag = 1; //加入的是数字
                            str--;
                        }
                        break;
                }
            }else{
                //第一个运算符，此时运算符栈是空的
                if(num_before_flag == 0){ //前面没有数字入栈
                    if(*str == '-'){ //此时'-'号表示为负号
                        opnd_stack->push(opnd_stack,str);//'-'号加入操作数栈
                        num_before_flag = 1; //加入的是数字
                    }else if(*str == '('){
                        optr_stack->push(optr_stack,str);  
                        elem = ' '; //数字字符加入空格间隔符
                        opnd_stack->push(opnd_stack,&elem);
                        num_before_flag = 0;//加入运算符
                    }else{
                        printf("Expression format error!");
                        break;
                    }
                }else{ //前面有数字入栈
                    optr_stack->push(optr_stack,str);  
                    elem = ' '; //数字字符加入空格间隔符
                    opnd_stack->push(opnd_stack,&elem);
                    num_before_flag = 0;//加入运算符
                }
            }
        }else{
            if(*str >= 0x30 && *str <= 0x39){
                opnd_stack->push(opnd_stack,str);
                num_before_flag = 1; //加入的是数字
            }
        }
        str++;
    }
    if(*str == '\0'){ //输入完成
        while(optr_stack->length(optr_stack)){
            optr_stack->pop(optr_stack,&opetr_char);//取运算符
            if(isOpetrChar(opetr_char)<5){
                number_b = getOpndNumFromStack(opnd_stack);
                number_a = getOpndNumFromStack(opnd_stack);
                cal_result = operate(number_a,opetr_char,number_b);
                printf("%d",number_a);
                printf(" %c ",opetr_char);
                printf("%d = ",number_b);
                printf("%d\n",cal_result);
                pushResultToStack(opnd_stack, cal_result);
            }
        }
    }
    DestroyLinearListStack(optr_stack);
    return opnd_stack;
}

int main(void)
{
    int i;
    char string[1000];
    LinearListStack *optr_result = NULL;
    printf("please enter a expression:");
    gets(string);
    optr_result = evaluateExpression(string);
    printf("%s = ",string);
    optr_result->risePrint(optr_result);
    DestroyLinearListStack(optr_result);
    return 0;
}

编译：

gcc LinearListStack.c LinearListStack.h EvaluateExpression.c -o EvaluateExpression

运行EvaluateExpression：

please enter a expression:3+3+(4*5）
3 + 3 = 6
4 * 5 = 20
6 + 20 = 26
3+3+(4*5） = 26

please enter a expression:-2+3+4*5
-2 + 3 = 1
4 * 5 = 20
1 + 20 = 21
-2+3+4*5 = 21

please enter a expression:-2+(3+4)*-5
3 + 4 = 7
7 * -5 = -35
-2 + -35 = -37
-2+(3+4)*-5 = -37

please enter a expression:3+3+((4*5))
3 + 3 = 6
4 * 5 = 20
6 + 20 = 26
3+3+((4*5)) = 26

please enter a expression:-2+(3/4)*-5
3 / 4 = 0
0 * -5 = 0
-2 + 0 = -2
-2+(3/4)*-5 = -2

please enter a expression:-2+(3%4)*-5
3 % 4 = 3
3 * -5 = -15
-2 + -15 = -17
-2+(3%4)*-5 = -17