算术表达式求值演示（C语言）
/*测试用例：演示用算符优先法演示对算术表达式求值的过程，主要对以下几个计算式进行演示：
8；1+2+3+4；88-1*5；1024/4*8；1024/(4*8)；(20+2)*(6/2)；
3-3-3；8/(9-8)；2*(6+2*(3+6*(6+6)))；(((6+6)*6+3)*2+6)*2
@Author:MJW
@学号：090502108
@班级：09信管1班
@完成时间:2010/12/22
*/
//头文件预处理命令
#include<stdio.h>
#include<stdlib.h>
//----------函数结果状态代码-----------------
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2
//----------定义函数类型，返回结果状态代码--------
typedef int Status;
//-----------定义栈的元素类型------------
typedef int ElemType;
//---------栈的顺序存储表示------------------
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
//-----------顺序栈的定义，并定义栈顶和栈底元素-----------
typedef struct{
ElemType *base;
ElemType *top;
int stacksize;
}Stack;
//--------基本操作的函数原型说明-----------
Status IfEmptyStack(Stack S);
Status InitStack (Stack &S);
Status EmptyStackEmpty(Stack &S);
Status GetTop(Stack S,ElemType &e);
Status Push(Stack &S,ElemType e);
Status Pop(Stack &S,ElemType &e);
Status ShowStack(Stack S);
Status EvaluateExpression();
//-------------In函数-----------------
int In(char ch);
char Precede(char a, char b);//判定运算符栈的栈顶运算符i与读入的运算符j之间优先关系的函数
int Operate(int a, char f, int b);
//--------基本操作的算法描述---------------
Status IfEmptyStack(Stack S){
if(S.base==S.top)
return 1;
return 0;
}//IfEmptyStack
Status InitStack(Stack &S){
//构造一个空栈
S.base=(ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType));
if(!S.base)exit(OVERFLOW);//存储分配失败
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
return 1;
}//InitStack
Status EmptyStack(Stack &S){
S.top=S.base;
return OK;
}//EmptyStack
Status GetTop(Stack S) {
//若栈不空，则用e返回S的栈顶元素，并返回OK，否则，返回ERROR
ElemType e;
e=*(S.top-1);
return e;
}//GetTop
Status Push(Stack &S,ElemType e){
//插入元素e为新的栈顶元素
if(S.top-S.base>=S.stacksize){//若栈满，则追加存储空间
S.base=(ElemType *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(ElemType));
if(!S.base) exit (OVERFLOW);//存储分配失败
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*S.top++=e;
return OK;
}//Push
Status Pop(Stack &S,ElemType &e){
//若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK，否则返回ERROR
if(S.top==S.base) return ERROR;
e=*--S.top;
return OK;
}//Pop
Status ShowStack(Stack S){
ElemType *p=S.base;
while(p!=S.top)
printf("%d",*p++);
return 1;
}//ShowStack
int In(char ch){
int res;
switch(ch) {
case '+':
case '-':
case '*':
case '/':
case '(':
case ')':
case '#': res=1;break;
default: res=0;break;
}
return res;
}//In
char Precede(char a, char b){
int i,j;
int form[7][7]=
{
{1,1,-1,-1,-1,1,1},
{1,1,-1,-1,-1,1,1},
{1,1,1,1,-1,1,1},
{1,1,1,1,-1,1,1},
{-1,-1,-1,-1,-1,0,2},
{1,1,1,1,2,1,1},
{-1,-1,-1,-1,-1,2,0}
};
switch(a) {
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;
}
switch(b) {
case '+':j=0;break;
case '-':j=1;break;
case '*':j=2;break;
case '/':j=3;break;
case '(':j=4;break;
case ')':j=5;break;
case '#':j=6;break;
}
if(form[i][j]==1)
return '>';//i的优先级高于j
else if(form[i][j])
return '<';//i的优先级低于j
else
return '=';//i的优先级等于j
}//Precede
int Operate(int a, char f, int b){
switch(f) {
case '+': return a+b;
case '-': return a-b;
case '*': return a*b;
case '/': return a/b;
}
return 0;
}//Operate
//-------------核心算法-------------------------
Status EvaluateExpression(){
//算术表达式求值的算符优先算法，设OPTR和OPND分别为运算符栈和运算数栈
char c, d[100];
int i, f, num, tmpa, tmpb;
Stack OPTR, OPND;
InitStack(OPTR);InitStack(OPND);
Push(OPTR, '#');
c=getchar();
while(c!='#'||GetTop(OPTR)!='#') {
if(c>='0'&&c<='9') {
i=0;
do{
d[i++]=c;
c=getchar();
}while(c>='0'&&c<='9');
d[i]='\0';
num=atoi(d);
Push(OPND, num);
}//if
else if(In(c)) {
switch(Precede(GetTop(OPTR), c)){
case '<'://栈顶元素优先权低
Push(OPTR, (int)c);c=getchar();
break;
case '=': //脱括号并接收下一字符
Pop(OPTR, f);c=getchar();
break;
case '>': //退栈并将运算结果入栈
Pop(OPTR, f);
Pop(OPND, tmpb); Pop(OPND, tmpa);
Push(OPND, Operate(tmpa, f, tmpb));
break;
}//switch
}//else if
}//while
c=getchar();//接收最后输入的一个回车符！！！否则在主函数中只能输入一次...
printf("所求表达式的值为：");
ShowStack(OPND);
printf("\n");
return 1;
}//EvaluateExpression
//-----------------主函数---------------------------
int main(){
system("color 69");//设置控制台背景及前景颜色
printf("\n\n\n");
printf(" 数据结构课程设计 \n\n");
printf(" ★★★★★★★★★★★★★★★★★★★★★\n");
printf(" \n");
printf(" 演示课题： 算术表达式求值演示 \n");
printf(" \n");
printf(" 姓名学号： MJW 090502108 \n");
printf(" \n");
printf(" 所在班级： 09信息管理1班 \n");
printf(" \n");
printf(" ★★★★★★★★★★★★★★★★★★★★★\n");
printf("请输入表达式，以 # 结束...\n");
//循环输入表达式，用while语句
while(1) {
EvaluateExpression();
printf("请再输入表达式，以 # 结束...\n");
}//while
return 0;
}//main
