experiment aim

实验

目

的

设计一个程序，演示用算符优先法对算术表达式求值的过程。利用算符优先关系，实现对算术四则混合运算表达式的求值。

（1）输入的形式：表达式，例如2*(3+4)#

包含的运算符只能有'+' 、'-' 、'*' 、'/' 、'('、 ')'，“#”代表输入结束符；

（2）输出的形式：运算结果，例如2*(3+4)=14；

（3）程序所能达到的功能：对表达式求值并输出。

实验思路

Experimental idea

为了实现用栈计算算数表达式的值，需设置两个工作栈：用于存储运算符的栈opter，以及用于存储操作数及中间结果的栈opnd。

（1）首先将操作数栈opnd设为空栈，而将'#'作为运算符栈opter的栈底元素，这样的目的是判断表达式是否求值完毕。

（2）依次读入表达式的每个字，表达式须以'#'结，读入字符若是操作数则入栈opnd，读入字符若是运算符，则将此运算符c与opter的栈顶元素top比较优先级后执行相应的操作，具体操作如下：

(i)若top的优先级小于c，即top<c< span="">，则将c直接入栈opter，并读入下一字符赋值给c；

(ii)若top的优先级等于c，即top=c，则弹出opter的栈顶元素，并读入下一字符赋值给c，这一步目的是进行括号操作;

（iii）若top优先级高于c，即top>c，则表明可以计算，此时弹出opnd的栈顶两个元素，并且弹出opter栈顶的的运算符，计算后将结果放入栈opnd中。直至opter的栈顶元素和当前读入的字符均为'#'，此时求值结束。

程序

1

● 应用跨工程公共代码头文件，标准库头文件以及一些变量的宏定义。

程序

2

●设置栈的结构体。

程序

3

● 一些需要用到的函数的编写，包括构造栈的函数、返回栈顶元素的函数、插入操作函数、删除操作函数、清空栈的函数和比较算符优先级的函数。

●

算符间的优先关系如下表所示（表来源：严蔚敏《数据结构》）：

表中需要注意的是θ1为opter的栈顶元素，θ2为从表达式中读取的操作符，此优先级表可以用二维数组实现。

程序

4

● 运算函数的编写。

程序

5

● 编写主函数并加以测试。

英文翻译

Data Structure (16) Using Stack to Realize Operator-First Calculator

Objective of the experiment: Design a program that demonstrates the process of evaluating arithmetic expressions using operator precedence. Using the operator precedence relationship, the evaluation of the mixed expression of the four arithmetic operations is realized.

(1) Input form: expression, such as 2*(3+4)#

The included operators can only have '+', '-', '*', '/', '(', ')', "#" represents the input terminator;

(2) The form of the output: the result of the operation, such as 2*(3+4)=14;

(3) The function that the program can achieve: evaluate the expression and output it.

Experimental idea: In order to use the stack to calculate the value of an arithmetic expression, two working stacks need to be set up: the stack opter for storing operators, and the stack opnd for storing operands and intermediate results.

(1) First, set the operand stack opnd as an empty stack, and use '#' as the bottom element of the operator stack opter, so as to judge whether the expression has been evaluated.

(2) Read each word of the expression in turn. The expression must be terminated with '#'. If the read character is an operand, it will be pushed into the stack opnd. If the read character is an operator, the stack of this operator c and opter will be used. The top element top performs the corresponding operation after comparing the priority. The specific operations are as follows:

(i) If the priority of top is less than c, that is, top<c, then="" put="" c="" directly="" into="" the="" stack="" opter,="" and="" read="" next="" character="" assign="" it="" to="" c;<="" div="">

(ii) If the priority of top is equal to c, that is, top=c, the top element of the stack of opter is popped, and the next character is read and assigned to c. The purpose of this step is to perform bracket operation;

(iii) If the top priority is higher than c, that is, top>c, it means that the calculation can be performed. At this time, the top two elements of the opnd stack are popped, and the operator at the top of the opter stack is popped. After the calculation, the result is put into the stack opnd. middle. Until the top element of the stack of opter and the currently read character are both '#', the evaluation ends.

The first step of the program: apply the cross-project common code header file, the standard library header file and the macro definitions of some variables.

The second step of the program: set the structure of the stack.

The third step of the program: write some functions that need to be used, including the function of constructing the stack, the function of returning the top element of the stack, the function of inserting operation, the function of deleting operation, the function of clearing the stack and the function of comparing operator priority.

The priority relationship between operators is shown in the following table (table source: Yan Weimin "Data Structure"):

It should be noted in the table that θ1 is the top element of the opter stack, and θ2 is the operator read from the expression. This priority table can be implemented with a two-dimensional array.

The fourth step of the program: the writing of the operation function.

The fifth step of the program: write the main function and test it.

参考资料：百度百科，重庆邮电大学数据结构课程PPT内容。

翻译：谷歌翻译。

本文由LearningYard新学苑原创，部分文字图片来源于他处，如有侵权，请联系删除。