简单四则运算表达式求值(栈的应用)

要求从键盘输入一个算术表达式并输出它的结果，算术表达式可包含加、减、乘、除、十进制整数和小括号，利用栈实现。

首先我们需要定义两个栈的基本创建插入删除操作
数据栈：存放数据
操作符栈：存放操作符

#include <stdio.h>
#include <stdlib.h> 
typedef int ElemType;
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
typedef struct //定义数据栈(存放数据) 
{ ElemType *base;
  ElemType *top;
  int stacksize;
 }SqStack; 
 typedef struct //定义操作符栈 
 { char *base;
   char *top;
   int stacksize;
 }OpStack;
int InitStack(SqStack &s) //初始化数据栈 
{	s.base=(ElemType *)malloc(STACK_INIT_SIZE*sizeof(ElemType));
 	if(!s.base) return 0;
 	s.top=s.base;
 	s.stacksize=STACK_INIT_SIZE;
 	return 1;
 } 
 int Push(SqStack &s,ElemType e) //数据栈的进栈操作 
 { if(s.top-s.base>=s.stacksize)
   {s.base=(ElemType *)realloc(s.base,(s.stacksize+STACKINCREMENT)*sizeof(ElemType));  
   if(!s.base) return 0;
   s.top=s.base+s.stacksize;
	s.stacksize+=STACKINCREMENT;
   }
   *s.top++=e;
 	return 1;
 }
 int Pop(SqStack &s,ElemType &e) //数据栈的出栈操作 
 { if(!s.base) return 0;
   e=*--s.top;
   return 1;
 }
 int InitOpStack(OpStack &s) //初始化操作符栈 
{	s.base=(char *)malloc(STACK_INIT_SIZE*sizeof(char));
 	if(!s.base) return 0;
 	s.top=s.base;
 	s.stacksize=STACK_INIT_SIZE;
 	return 1;
 } 
 int OpPush(OpStack &s,char e) //操作符栈的进栈操作 
 { if(s.top-s.base>=s.stacksize)
   {s.base=(char *)realloc(s.base,(s.stacksize+STACKINCREMENT)*sizeof(char));  
   if(!s.base) return 0;
   s.top=s.base+s.stacksize;
	s.stacksize+=STACKINCREMENT;
   }
   *s.top++=e;
 	return 1;
 }
 int OpPop(OpStack &s,char &e) //操作符栈的出栈操作 
 { if(!s.base) return 0;
   e=*--s.top;
   return 1;
 }

然后定义一个运算符比较表来告诉系统这些基本运算符的优先顺序。

char Precede(char a1,char a2) //运算符比较表 
 {  switch(a1){
  case '+':
  	switch(a2){
  		case '+':return '>';
  		case '-':return '>';
  		case '*':return '<';
  		case '/':return '<';
  		case '(':return '<';
  		case ')':return '>';
  		case '#':return '>';
  		}
 case '-':
  	switch(a2){
  		case '+':return '>';
  		case '-':return '>';
  		case '*':return '<';
  		case '/':return '<';
  		case '(':return '<';
  		case ')':return '>';
  		case '#':return '>';
  		}
  case '*':
  	switch(a2){
  		case '+':return '>';
  		case '-':return '>';
  		case '*':return '>';
  		case '/':return '>';
  		case '(':return '<';
  		case ')':return '>';
  		case '#':return '>'; 
		}
  case '/':
  	switch(a2){
  		case '+':return '>';
  		case '-':return '>';
  		case '*':return '>';
  		case '/':return '>';
  		case '(':return '<';
  		case ')':return '>';
  		case '#':return '>';
		}
 case '(':
  	switch(a2){
  		case '+':return '<';
  		case '-':return '<';
  		case '*':return '<';
  		case '/':return '<';
  		case '(':return '<';
  		case ')':return '=';
  		case '#':return 0;
  		}
 case ')':
  	switch(a2){
  		case '+':return '>';
  		case '-':return '>';
  		case '*':return '>';
  		case '/':return '>';
  		case '(':return 0;
  		case ')':return '>';
  		case '#':return '>';
  		}
 case '#':
  	switch(a2){
  		case '+':return '<';
  		case '-':return '<';
  		case '*':return '<';
  		case '/':return '<';
  		case '(':return '<';
  		case ')':return 0;
  		case '#':return '=';
		}
	}
 }

定义函数（对从栈顶取出的两个数进行操作）

ElemType Operate(ElemType a,char theta,ElemType b) //两个数的操作 
{  ElemType  sum;
	switch(theta) //对传递的运算符进行相应操作 
	{ case '+':sum=a+b;break;
	  case '-':sum=a-b;break;
	  case '*':sum=a*b;break;
	  case '/':sum=a/b;break;	
	}
	return sum;
}

然后通过表达式求值算法函数调用前面所说函数进行计算

int EvaluateExpression() //表达式求值 
 { SqStack OPND;
   OpStack OPTR;
 	char c,e,theta; //c为输入字符 e，theta为下面删除变量 
 	ElemType b,a; //ba为下面的删除变量 
   InitOpStack(OPTR);OpPush(OPTR,'#'); //初始化两个栈 并且将#进入操作符栈底 
   InitStack(OPND);
   printf("输入表达式(输入#结束)：\n");
   c=getchar();
   while(c!='#'||*(OPTR.top-1)!='#') //当输入的字符不为#或者操作符栈顶指针不指向栈底 
   {  if(c>='0'&&c<='9') //如果字符为数字 
     { Push(OPND,c-48); //进数字栈 
       c=getchar();
     }
     else //如果为运算符 
     {
      switch(Precede(*(OPTR.top-1),c)) //比较操作符栈顶指针与输入字符优先级 
      { case '<':OpPush(OPTR,c);c=getchar();break;//如果小于 继续进栈 
        case '=':OpPop(OPTR,e);c=getchar();break; //等于 删除 
        case '>':OpPop(OPTR,theta);Pop(OPND,b);Pop(OPND,a); //大于 提取数字栈顶的两个数进行运算 
        		Push(OPND,Operate(a,theta,b)); //将运算完成的数进栈 
        		break;
      	
	  }
	}
   }
   printf("表达式的值=:%d",*(OPND.top-1)); 
   return 1;
 }

然后在主函数中调用，查看运行结果

int main()
 { 
 	EvaluateExpression();
 	return 0;
 }