（数据结构实验）栈的应用－算术表达式求值

短命女 2022-04-14 04:42 751阅读 0赞

### 实验目的： ###

1．掌握栈的定义及实现；

2．掌握利用栈求解算术表达式的方法。

### 实验内容： ###

通过修改完善教材中的算法3.22，利用栈来实现算术表达式求值的算法。

**对算法3.22中调用的几个函数要给出其实现过程：**

(1) 函数In(c)：判断c是否为运算符；

(2) 函数Precede(t1,t2)：判断运算符t1和t2的优先级；

(3) 函数Operate(a,theta,b)：对a和b进行二元运算theta。

**栈的定义和实现(使用链栈实现以下的函数)：**

(1) 函数InitStack的实现 见算法 3.5

(2) 函数Push的实现 见算法 3.6

(3) 函数Pop的实现 见算法 3.7

(4)函数GetTop的实现 见算法 3.8

### 实验代码： ###

#include<stdio.h>
    const char oper[7] = { '+', '-', '*', '/', '(', ')', '#' };
    
    #define OK 1
    #define ERROR 0
    #define OVERFLOW -2
    
    typedef char SElemType;
    typedef int Status;
    typedef struct SNode {
    	int data;
    	struct SNode *next;
    } SNode, *LinkStack;
    
    //构造一个空栈
    Status InitStack(LinkStack &S) {
    	S = NULL;
    	return OK;
    }
    
    //判断是否为空栈
    bool StackEmpty(LinkStack S) {
    	if (!S)
    		return true;
    	return false;
    }
    
    //用e返回S的项元素
    Status GetTop(LinkStack &S) {
    	if (!S)
    		return ERROR;
    
    	return S->data;
    }
    
    //插入e为新的项元素
    Status Push(LinkStack &S, SElemType e) {
    	SNode *p = new SNode;
    	if (!p) {
    		return OVERFLOW;
    	}
    	p->data = e;
    	p->next = S;
    	S = p;
    	return OK;
    }
    
    //删除S的项元素，并用e返回其值
    Status Pop(LinkStack &S, SElemType &e) {
    	SNode *p;
    	if (!S)
    		return ERROR;
    	e = S->data;
    	p = S;
    	S = S->next;
    	delete p;
    	return OK;
    }
    
    /*判断输入的某个字符是否是运算符
     *ch表示输入的字符
     *oper数组中存放系统能识别的运算符
     */
    bool In(char ch) {
    	for (int i = 0; i < 7; i++) {
    		if (ch == oper[i]) {
    			return true;
    		}
    	}
    	return false;
    }
    
    /*比较两个运算符的优先级
     *a，b中存放待比较的运算符
     */
    char Precede(char a, char b) {
    	if ((a == '(' && b == ')') || (a == '#' && b == '#')) {
    		return '=';
    	} else if (a == '(' || a == '#' || b == '(' || (a == '+' || a == '-') && (b == '*' || b == '/')) {
    		return '<';
    	} else
    		return '>';
    }
    
    /*进行两数的运算
     *a，b中分别以char型存放两个待运算的操作数
     *theta中存放代表操作符的字符
     *结果以char型返回
     */
    char Operate(char a, char theta, char b) {
    	switch (theta) {
    	case '+':
    		return (a - '0') + (b - '0') + 48;
    	case '-':
    		return (a - '0') - (b - '0') + 48;
    	case '*':
    		return (a - '0') * (b - '0') + 48;
    	case '/':
    		return (a - '0') / (b - '0') + 48;
    	}
    	return 0;
    }
    
    //算法3.22　表达式求值
    char EvaluateExpression() {//算术表达式求值的算符优先算法，设OPTR和OPND分别为运算符栈和操作数栈
    
    	LinkStack OPTR, OPND;
    	char ch, theta, a, b, x, top;
    
    	InitStack(OPND); //初始化OPND操作数栈
    	InitStack(OPTR); //初始化OPTR运算符栈
    	Push(OPTR, '#'); //将表达式起始符“#”压入OPTR栈
    
    	scanf("%c",&ch);
    	while (ch != '#' || (GetTop(OPTR) != '#')) //表达式没有扫描完毕或OPTR的栈顶元素不为“#”
    	{
    		if (!In(ch)) {
    			Push(OPND, ch);
    			scanf("%c",&ch);
    		} //ch不是运算符则进OPND栈
    		else
    			switch (Precede(GetTop(OPTR), ch)) //比较OPTR的栈顶元素和ch的优先级
    			{
    			case '<': //栈顶元素优先级低
    				Push(OPTR, ch);
    				scanf("%c",&ch); //当前字符ch压入OPTR栈，读入下一字符ch
    				break;
    			case '>':
    				Pop(OPTR, theta); //弹出OPTR栈顶的运算符
    				Pop(OPND, b);
    				Pop(OPND, a); //弹出OPND栈顶的两个运算数
    				Push(OPND, Operate(a, theta, b)); //将运算结果压入OPND栈
    				break;
    			case '=': //OPTR的栈顶元素是“(”且ch是“)”
    				Pop(OPTR, x);
    				scanf("%c",&ch); //弹出OPTR栈顶的“(”，读入下一字符ch
    				break;
    			} //switch
    	} //while
    	return GetTop(OPND); //OPND栈顶元素即为表达式求值结果
    }
    
    int menu() {
    	int c;
    	printf("0-9以内的多项式计算\n" );
    	printf("1.计算\n");
    	printf("0.退出\n");
    	printf("选择：");
    	scanf("%d",&c);
    	return c;
    }
    
    int main() {
    	do
    	{
    		switch (menu()) {
    		case 1: {
    			printf("请输入要计算的表达式（操作数和结果都在0-9的范围内，以#结束）：\n如 2+2# \n" );
    			char res = EvaluateExpression();//算法3.22　表达式求值
    			printf("计算结果为%d\n",res - 48);
    			printf("--------------------------------------\n");
    		}
    			break;
    		case 0:
    			printf("退出成功\n");
    			return 0;
    		default:
    			break;
    		}
    	}
    	while (1);
    
    	return 0;
    }

### 结果示例： ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2R5d182NjY2NjY_size_16_color_FFFFFF_t_70][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2R5d182NjY2NjY_size_16_color_FFFFFF_t_70]: /images/20220414/7fc9129822094216a75f515dcbb6e995.png