《數(shù)據(jù)結(jié)構(gòu)（C語言版）》棧的應(yīng)用之表達(dá)式求值
清華大學(xué)計(jì)算機(jī)系列教材? ?累計(jì)發(fā)行超400萬冊
嚴(yán)蔚敏 吳偉明 編著
數(shù)據(jù)結(jié)構(gòu)（C語言版）?
以下是本人對紫皮書第三章3.2節(jié)棧的應(yīng)用舉例中3.2.5表達(dá)式求值的代碼，3.2.4迷宮求解已在上節(jié)給出，3.2.1數(shù)制轉(zhuǎn)換、3.2.2括號匹配的檢驗(yàn)、3.2.3行編輯程序的代碼已在上上節(jié)寫出
注：感覺課本上的代碼有點(diǎn)問題，只能處理操作數(shù)為10以內(nèi)的表達(dá)式的值，不能計(jì)算40*2，因?yàn)樗?0的個(gè)位和十位同等對待壓入棧，但本人能力有限不知道怎么改，有時(shí)間再回來看看
上運(yùn)行結(jié)果：
代碼如下：
#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;//操作數(shù)類型，可能是int,float,double,這里以int為例
typedef char SElemType;
typedef int Status;
typedef struct
{
SElemType* base;
SElemType* top;
int stacksize;//當(dāng)前已分配的存儲空間，以元素為單位
}SqStack;
/*使用全局變量定義運(yùn)算符集合與算符間的優(yōu)先關(guān)系*/
char OP[7] = { '+','-','*','/','(',')','#' };
char SymbolPriority[8][8] = { ' ','+','-','*','/','(',')','#',
'+','>','>','<','<','<','>','>',
? ? ?'-','>','>','<','<','<','>','>',
'*','>','>','>','>','<','>','>',
'/','>','>','>','>','<','>','>',
'(','<','<','<','<','<','=',' ',
')','>','>','>','>',' ','>','>',
'#','<','<','<','<','<',' ','='};
Status InitStack(SqStack& S);//初始化一個(gè)空棧
SElemType GetTop(SqStack& S);//返回棧頂元素，若為空則返回ERROR
Status Push(SqStack& S, SElemType e);//順序棧的入棧
Status Pop(SqStack& S, SElemType& e);//順序棧的出棧
Status In(char c, char* p);//判斷是否為運(yùn)算符
Status Precede(char m, char n);//判斷運(yùn)算符優(yōu)先級
SElemType Operate(SElemType a, char theta, SElemType b);//計(jì)算
SElemType EvaluateExpression();//算術(shù)表達(dá)式求值的算符優(yōu)先算法
int main()
{
printf("計(jì)算器已啟動(dòng)，您可以計(jì)算表達(dá)式的值，并以#結(jié)束您的輸入\n");
printf("例如：您可以輸入? 3-(4/2*3-1)+2*7#? 來計(jì)算其值\n");
int result = EvaluateExpression();
printf("答案為：%d", result);
return 0;
}
SElemType EvaluateExpression()//算術(shù)表達(dá)式求值的算符優(yōu)先算法
{
SqStack OPTR;//運(yùn)算符棧，用以寄存運(yùn)算符OPeraToR(operator)
SqStack OPND;//運(yùn)算數(shù)棧，用以寄存操作數(shù)或運(yùn)算結(jié)果OPeraND(operand)(操作數(shù))
InitStack(OPTR);
Push(OPTR, '#');
InitStack(OPND);
char c = getchar();
SElemType x;
char theta;
while (c != '#' || GetTop(OPTR) != '#')
{
if (!In(c, OP))//不是運(yùn)算符則進(jìn)棧
{
c -= '0';//將字符1-9轉(zhuǎn)換為對應(yīng)ASCII碼值進(jìn)行計(jì)算
Push(OPND, c);
c = getchar();
}
else
{
switch (Precede(GetTop(OPTR),c))
{
case '<'://棧頂元素優(yōu)先權(quán)低
Push(OPTR, c);
c = getchar();
break;
case '='://可以觀察到課本p53表3.1中僅在右括號與左括號匹配或右井號與左井號匹配時(shí)取等
Pop(OPTR, x);
c = getchar();
break;
case '>':
theta = GetTop(OPTR);
Pop(OPTR, theta);//將即將優(yōu)先級高的運(yùn)算符退棧
SElemType b;
Pop(OPND, b);//將參與本次運(yùn)算的右邊的操作數(shù)退棧
SElemType a;
Pop(OPND, a);//將參與本次運(yùn)算的左邊的操作數(shù)退棧
Push(OPND, Operate(a, theta, b));//計(jì)算結(jié)果并入棧
printf("正在計(jì)算%d%c%d=%d\n", a, theta, b, Operate(a, theta, b));
break;
}
}
}
return GetTop(OPND);
}
Status Precede(char m, char n)//判斷運(yùn)算符優(yōu)先級
{
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下的坐標(biāo)
}
SElemType Operate(SElemType a, char theta, SElemType b)//計(jì)算
{
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)//判斷是否為運(yùn)算符
{
for (int i = 0; i < 7; i++)
{
if (c == *p)
{
return TRUE;
}
p++;
}
return FALSE;
}
Status InitStack(SqStack& S)//初始化一個(gè)空棧
{
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
//這里和上一節(jié)棧的基本功能不太一樣，直接返回棧頂元素而不采用引用的方式，更便捷
{
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;
}
