使用堆栈实现对算数四则混合运算表达式的求值（C语言）

---

一、问题分析

基本思路

想要用算法来计算一个算术表达式（字符串），要能够正确地解释表达式。首先，明确一下四则运算的基本规则：

• 先乘除，后加减
• 从左到右计算
• 先括号内，后括号外

可以在一边入栈的过程中，一边根据运算规则一步步计算式子。问题在于堆栈如何设置。假设是一个简单的不含括号的四则运算，尝试只使用一个堆栈来解决问题。举个例子：

e.g. 3+4*5-1#（#作为结束符）
1、首先3入栈，+入栈，下一个字符是4，这个时候就遇到一个问题，在不知道下一个字符是乘除还是加减的情况下，不能进行3+4的计算。
2、于是4也入栈，读取下一个字符，发现是 *，于是 * 入栈
3、读取下一个字符5，同时读取栈顶发现是 * ，可以计算，于是 * 出栈，4出栈，4 * 5 得到20并暂存。
4、读取栈顶字符发现是 + ，读取下一个字符，发现是 - ，所以要进行3+20的计算
5、类似，后续计算过程省略

观察上述计算过程，我们发现在判断是否执行一步计算的时候，首先要做的是判断相邻两个运算符的优先级，然后才能决定是否进行计算。这给我们一种启发，设置两个堆栈，运算符堆栈（OPRT）与运算数堆栈（OPND），分别存储运算符（Operator）与运算数（Operand），将使进出栈的步骤简化，判断算符优先级的过程更为容易。

算符优先级构建

我们用> 、=、<来简单表示左算符sym1与右算符sym2对比下的优先级。sym1存在算符栈栈顶，而sym2为刚从字符串中读取到的字符。

1. sym1>sym2 执行sym1的计算，sym1出栈
2. sym1<sym2 sym2进栈
3. sym1=sym2 左右括号相遇，表示括号内计算完成，sym1出栈，sym2清空

列表如下：

注：是算符优先级对比表格

sym1\sym2	+	-	*	/	(	)	#
+	>	>	<	<	<	>	>
-	>	>	<	<	<	>	>
*	>	>	>	>	<	>	>
/	>	>	>	>	<	>	>
(	<	<	<	<	<	=	EORROR
)	>	>	>	>	ERROR	>	>
#	<	<	<	<	<	ERROR	=

1、乘除优先级大于加减，同级运算符处于左侧时优先级更大
2、sym1=‘(’ 时，要进行该括号右侧的运算，sym2应当入栈所以sym1<sym2
3、sym2=’(‘ 时，要进行该括号右侧的运算，此时sym2应当入栈所以sym1<sym2
4、sym2=’)’ 时，要进行该括号左侧的运算，并使sym1出栈，所以sym1>sym2
5、sym1=‘(’ 且sym2=’)’时表示括号内运算完成，消去一对括号，所以sym1=sym2
6、一般来说，‘)’ 在括号内计算结束后就被消去了，没有入栈的情况，因此若 ‘)’ 在栈内，应当进行消括号的操作，将消括号的操作定义为 “ ’)’ 的运算”
7、‘#’ ‘#’表示表达式计算完成（在栈底放置’#‘ 用来与结束符对应）
8、几种表达式错误的情况：’)’ num ‘(‘ ，’#’ num ‘)’，’(‘ num ‘#’ ，在表达式括号不匹配时会出现以上情况，应当报错

二、算法描述

• 设置两个工作栈，OPTR寄存运算符，OPND寄存运算数或者中间运算结果
• 首先置操作数栈为空栈，起始符 ’#‘ 作为栈底元素
• 依次读入表达式字符，运算数进OPND栈，运算符和栈顶元素进行优先级比较后再进行相应操作。
• OPTR中栈顶元素与当前读入字符均为’#‘时求值结束，结果输出

  算法描述

  OperandType EvaluateExpression(){
  //OP为运算符合集
  InitStack(OPTR); Push(OPTR,'#');
  InitStack(OPND); c=getchar();
  while(c!=#||GetTop(OPTR)!='#'){
  	if(!In(c,OP)){Push(OPND,c); c=getchar(); }  //不是运算符则进栈
  	else
  		switch(Precede(GetTop(OPTR),c)){
  			case'<':	//符号入栈
  				Push(OPTR,c); c=getchar();
  				break;
  			case'=':	//脱括号并接收下一个字符
  				Pop(OPTR,x); c=getchar();
  				break;
  			case'>':	//退栈并将运算结果入栈
  				Pop(OPTR,theta);
  				Pop(OPND,b); Pop(OPND,a);
  				Push(OPND,Operate(a,theta,b));
  				break;
  			} //switch
  		} //while
  		return GetTop(OPND);	//返回运算结果
  	} //EvaluateExpression

  函数说明：

  InitStack(S) //构造一个空栈
  Push(S,e) //入栈
  Pop(S,x) //出栈
  GetTop(S) //返回栈顶元素
  In(c,OP) //比较，判断c是否为OP中的运算符
  Precede(c1,c2) //比较两个运算符c1与c2的优先级，并返回> = <
  Operate(num1,sym,num2) //执行运算操作，num1、num2为运算数，sym为运算符

  堆栈运算过程的直观体现

  e.g.3*(7-2)

  步骤	OPTR栈	OPND栈	输入字符	主要操作
  1	#		$\underline{3}$$\text{*}$(7-2) #	Push(OPND,’$\text{3}$’)
  2	#	3	$\underline{*}$(7-2) #	Push(OPTR,’ $\text{*}$ ‘)
  3	# $\text{*}$	3	$\underline{(}$ 7-2) #	Push(OPTR,’ $\text{(}$ ‘)
  4	# $\text{*}$ (	3	$\underline{7}$ -2) #	Push(OPND,’ $\text{7}$ ‘)
  5	# $\text{*}$ (	3 7	$\underline{-}$ 2) #	Push(OPTR,’ $\text{-}$ ‘)
  6	# $\text{*}$ ( -	3 7	$\underline{2}$ ) #	Push(OPND,’ $\text{2}$ ‘)
  7	# $\text{*}$ ( -	3 7 2	$\underline{)}$ #	Operate(‘7’ , ‘-‘ , ‘2’)
  8	# $\text{*}$ (	3 5	$\underline{)}$ #	Pop(OPTR) {消去一对括号}
  9	# $\text{*}$	3 5	#	Operate(‘3’ , ‘$\text{*}$’ , ‘5’)
  10	#	15	#	return(GetTop(OPND))

三、代码实现

源代码

• 基本思路同算法描述一致
• 更改输入方式为从文件输入

  #include<stdio.h>
  #include<stdlib.h>
  #include<math.h>
  #define ERROR -1        //报错返回值
  #define TRUE 1
  #define OK 0
  #define STACK_INIT_SIZE 30      //堆栈初始化分配空间
  #define STACKINCREMENT 50       //追加堆栈空间
  struct stack{           //堆栈结构体定义
      int *bottom;
      int *top;
      int stacksize;
  };
  
  int InitStack(stack &S);
  int push(stack &S,int ch);
  int pop(stack &S,int &ch);
  int GetTop(stack &S);
  int IsOptr(char ch);
  char Precede(int sym1,int sym2);
  int Operate(int a,int theta,int b);
  
  FILE *fp;
  
  int main(){
      stack OPTR,OPND;    //OPTR堆栈保存运算符，OPND堆栈保存运算数
      char c='0';         //c为从文件读取的当前字符
      int x,theta,a,b;    //x作为数值暂存器，theta存运算符，a,b分别为theta运算符前后的运算数
      fp=fopen("equation.txt","r");
      while(c!='@'){
          InitStack(OPTR); 
          push(OPTR,'#');
          InitStack(OPND); 
          c=fgetc(fp);
          while(c!='#' || GetTop(OPTR)!='#'){
              if(!IsOptr(c)){     //是否运算符，若不是则进行运算数压栈
                  push(OPND,c-48);
                  c=fgetc(fp);
                  while(!IsOptr(c)){      //多于一位字符的运算数需要多次处理
                      pop(OPND,x);
                      push(OPND,x*10+c-48);
                      c=fgetc(fp);
                  }
              }
              else
                  switch(Precede(GetTop(OPTR),c)){        //根据运算符优先级选择操作
                      case'<':push(OPTR,c);c=fgetc(fp);break;     //运算符压栈
                      case'=':pop(OPTR,x);c=fgetc(fp);break;      //运算符出栈
                      case'>':pop(OPTR,theta);                    //执行一次计算
                              pop(OPND,b);pop(OPND,a);
                              push(OPND,Operate(a,theta,b));
                              break;
                  }
          }
          printf("%d\n",GetTop(OPND));        //打印一个算术表达式的结果
          c=fgetc(fp);        //读取算术表达式后的字符，分回车符'\n'和文件结束符'@'两种情况
      }
      fclose(fp); 
      return 0;
  }
  
  int InitStack(stack &S){               //堆栈初始化
      S.bottom=(int *)malloc(STACK_INIT_SIZE*sizeof(char));
      if(!S.bottom) exit(OVERFLOW);
      S.top=S.bottom;
      S.stacksize=STACK_INIT_SIZE;
      return OK;
  }
  
  int push(stack &S,int ch){            //压栈
      if(S.top-S.bottom>=S.stacksize){
          S.bottom=(int*)realloc(S.bottom,S.stacksize+STACKINCREMENT*sizeof(int));
          if(!S.bottom) exit(OVERFLOW);
          S.top=S.bottom+S.stacksize;
          S.stacksize+=STACKINCREMENT;
      }
      *S.top=ch;
      S.top=S.top+1;
      return OK;
  }
  
  int pop(stack &S,int &ch){             //出栈
      if(S.top==S.bottom) return ERROR;
      ch=*(S.top-1);
      S.top--;
      *(S.top)=0;
      return OK;
  }
  
  int GetTop(stack &S){          //返回栈顶元素
      int ch;
      if(S.top==S.bottom) return ERROR;
      ch=*(S.top-1);
      return ch;
  }
  
  int IsOptr(char ch){                    //判断是否算符
      int i=0;
      char optr[]={'+','-','*','/','(',')','#','@'};
      while(optr[i]!='@'){
          if(ch==optr[i]) return TRUE;
          i++;
      }
      return OK;
  }
  
  char Precede(int sym1,int sym2){          //算符优先级判别
      if     (sym1=='#'&&sym2=='#') return '=';
      else if(sym1=='#'&&sym2==')') exit(ERROR);
      else if(sym1=='#')            return '<';
      else if(sym1=='('&&sym2=='#') exit(ERROR);
      else if           (sym2=='#') return '>';
      else if(sym1==')'&&sym2=='(') exit(ERROR);
      else if(sym1==')')            return '>';
      else if(sym1=='('&&sym2==')') return '=';
      else if           (sym2==')') return '>';
      else if(sym1=='(')            return '<';
      else if           (sym2=='(') return '<';
      else if(sym1=='*'||sym1=='/'||sym2=='+'||sym2=='-') return '>';
      else return '<';
  }
  
  int Operate(int a,int theta,int b){         //四则运算操作
      if(theta=='+') return a+b;
      else if(theta=='-') return a-b;
      else if(theta=='*') return a*b;
      else if(theta=='/'){
          if(b==0) {printf("该行除数为0，出错！"); return NULL;}
          else return a/b;
      } 
      else exit(ERROR);
  }

  测试数据

  “equation.txt”中填入如下的测试数据：

  3*(7-2)#
  8#
  1+2+3+4#
  88-15#
  1024/48#
  (20+2)(6/2)#
  3-3-3#
  8/(9-9)#
  2(6+2*(3+6*(6+6)))#
  (((6+6)*6+3)*2+6)*2#@

每行写一串表达式，以 ‘#‘ 结尾 ，‘@’为文件结束符

测试结果如下：

[Running] cd “d:\applications\VS_Code\CProFile" && g++ Arithmetic.cpp -o Arithmetic && “d:\applications\VS_Code\CProFile"Arithmetic
15
8
10
83
2048
66
-3
该行除数为0，出错！0
312
312
[Done] exited with code=0 in 1.935 seconds

四、一些说明

• 用逐个字符的方式读取文件，当整数有不止一位时，采用栈顶数乘十加当前读取位的方式保存完整数
• 本代码没有实现小数计算，若要实现此功能，需要加入小数点的判别
• 本代码实现带括号加减乘除的计算，若需要增加运算功能，如乘方、单目增、单目减等，需要在判断是否算符、算符优先级判别以及运算操作函数中再做增改
• 算法描述搬运自（《数据结构（C语言版）》严蔚敏，吴伟民）QwQ

我很可爱，请给我钱

• 本文作者：kuuhaku
• 本文链接：http://kuuhaku.top/posts/Arithmetic/
• 版权声明：本博客所有文章除特别声明外，均默认采用 许可协议。