《数据结构（C语言版）》栈的应用之表达式求值
清华大学计算机系列教材 累计发行超400万册
严蔚敏 吴伟明 编著
数据结构（C语言版）
以下是本人对紫皮书第三章3.2节栈的应用举例中3.2.5表达式求值的代码，3.2.4迷宫求解已在上节给出，3.2.1数制转换、3.2.2括号匹配的检验、3.2.3行编辑程序的代码已在上上节写出
注：感觉课本上的代码有点问题，只能处理操作数为10以内的表达式的值，不能计算40*2，因为它把40的个位和十位同等对待压入栈，但本人能力有限不知道怎么改，有时间再回来看看
上运行结果：
代码如下：
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
#define STACK_INIT_SIZE 100//存储空间初始分配量
#define STACKINCREMENT 10//存储空间分配增量
typedef int OperandType;//操作数类型，可能是int,float,double,这里以int为例
typedef char SElemType;
typedef int Status;
typedef struct
{
SElemType* base;
SElemType* top;
int stacksize;//当前已分配的存储空间，以元素为单位
}SqStack;
/*使用全局变量定义运算符集合与算符间的优先关系*/
char OP[7] = { '+','-','*','/','(',')','#' };
char SymbolPriority[8][8] = { ' ','+','-','*','/','(',')','#',
'+','>','>','<','<','<','>','>',
'-','>','>','<','<','<','>','>',
'*','>','>','>','>','<','>','>',
'/','>','>','>','>','<','>','>',
'(','<','<','<','<','<','=',' ',
')','>','>','>','>',' ','>','>',
'#','<','<','<','<','<',' ','='};
Status InitStack(SqStack& S);//初始化一个空栈
SElemType GetTop(SqStack& S);//返回栈顶元素，若为空则返回ERROR
Status Push(SqStack& S, SElemType e);//顺序栈的入栈
Status Pop(SqStack& S, SElemType& e);//顺序栈的出栈
Status In(char c, char* p);//判断是否为运算符
Status Precede(char m, char n);//判断运算符优先级
SElemType Operate(SElemType a, char theta, SElemType b);//计算
SElemType EvaluateExpression();//算术表达式求值的算符优先算法
int main()
{
printf("计算器已启动，您可以计算表达式的值，并以#结束您的输入\n");
printf("例如：您可以输入 3-(4/2*3-1)+2*7# 来计算其值\n");
int result = EvaluateExpression();
printf("答案为：%d", result);
return 0;
}
SElemType EvaluateExpression()//算术表达式求值的算符优先算法
{
SqStack OPTR;//运算符栈，用以寄存运算符OPeraToR(operator)
SqStack OPND;//运算数栈，用以寄存操作数或运算结果OPeraND(operand)(操作数)
InitStack(OPTR);
Push(OPTR, '#');
InitStack(OPND);
char c = getchar();
SElemType x;
char theta;
while (c != '#' || GetTop(OPTR) != '#')
{
if (!In(c, OP))//不是运算符则进栈
{
c -= '0';//将字符1-9转换为对应ASCII码值进行计算
Push(OPND, c);
c = getchar();
}
else
{
switch (Precede(GetTop(OPTR),c))
{
case '<'://栈顶元素优先权低
Push(OPTR, c);
c = getchar();
break;
case '='://可以观察到课本p53表3.1中仅在右括号与左括号匹配或右井号与左井号匹配时取等
Pop(OPTR, x);
c = getchar();
break;
case '>':
theta = GetTop(OPTR);
Pop(OPTR, theta);//将即将优先级高的运算符退栈
SElemType b;
Pop(OPND, b);//将参与本次运算的右边的操作数退栈
SElemType a;
Pop(OPND, a);//将参与本次运算的左边的操作数退栈
Push(OPND, Operate(a, theta, b));//计算结果并入栈
printf("正在计算%d%c%d=%d\n", a, theta, b, Operate(a, theta, b));
break;
}
}
}
return GetTop(OPND);
}
Status Precede(char m, char n)//判断运算符优先级
{
int mValue;
int nValue;
switch (m)
{
case '+':
mValue = 1;
break;
case '-':
mValue = 2;
break;
case '*':
mValue = 3;
break;
case '/':
mValue = 4;
break;
case '(':
mValue = 5;
break;
case ')':
mValue = 6;
break;
case '#':
mValue = 7;
break;
}
switch (n)
{
case '+':
nValue = 1;
break;
case '-':
nValue = 2;
break;
case '*':
nValue = 3;
break;
case '/':
nValue = 4;
break;
case '(':
nValue = 5;
break;
case ')':
nValue = 6;
break;
case '#':
nValue = 7;
break;
}
return SymbolPriority[mValue][nValue];//即对号入座，找到字符m与n在课本表3.1下的坐标
}
SElemType Operate(SElemType a, char theta, SElemType b)//计算
{
SElemType result;
switch (theta)
{
case '+':
result = a + b;
break;
case '-':
result = a - b;
break;
case '*':
result = a * b;
break;
case '/':
result = a / b;
break;
}
return result;
}
Status In(char c,char* p)//判断是否为运算符
{
for (int i = 0; i < 7; i++)
{
if (c == *p)
{
return TRUE;
}
p++;
}
return FALSE;
}
Status InitStack(SqStack& S)//初始化一个空栈
{
S.base = (SElemType*)malloc(STACK_INIT_SIZE * sizeof(SElemType));
if (!S.base)
{
exit(OVERFLOW);
}
S.top = S.base;
S.stacksize = STACK_INIT_SIZE;
return OK;
}
SElemType GetTop(SqStack& S)//返回栈顶元素，若为空则返回ERROR
//这里和上一节栈的基本功能不太一样，直接返回栈顶元素而不采用引用的方式，更便捷
{
if (S.top == S.base)
{
return ERROR;
}
return *(S.top - 1);
}
Status Push(SqStack& S, SElemType e)//顺序栈的入栈
{
if (S.top - S.base >= S.stacksize)
{
SElemType* New_ptr = (SElemType*)realloc(S.base, ((S.stacksize) + STACKINCREMENT) * sizeof(SElemType));
if (!New_ptr)
{
exit(OVERFLOW);
}
S.base = New_ptr;
S.top = S.base + S.stacksize;
S.stacksize += STACKINCREMENT;
}
*S.top++ = e;
return OK;
}
Status Pop(SqStack& S, SElemType& e)//顺序栈的出栈
{
if (S.top == S.base)
{
return ERROR;
}
e = *--S.top;
return OK;
}
