1.问题描述 （1）表达式求值问题 表达式是数据运算的基本形式。 人们的书写习 惯是中缀式，如：11+22*(7-4)/3。中缀式的计算按运算符的优先级及括号优先的原则，相同级别从左到右进行计算。表达式还有后缀式（如：22 7 4 - * 3 / 11 +）和前缀式（如：+ 11 / * 22 – 7 4 3）。后缀表达式和前缀表达式中没有括号，给计算带来方便。如后缀式计算时按运算符出现的先后进行计算。本设计的主要任务是进行表达式形式的转换及不同形式的表达式计算。 2.数据结构设计 （1）表达式求值问题 由于表达式中有字符与数字两种类型，故定义结点一个标志域 data，标志结点存储的为字符 data=2 还是数字 data=1，再寻找结点中对应的存储位置，读取数字域 data1,字符域 data2。而在前缀表达式时，存在表达式逆序，因表达式类型不统一，用栈逆序极不方便，选择构建双向链表，存储表达式。 typedef struct Node //定义存储中缀表达式的结点类型 {int data; int data1; char data2; struct Node *next; }Lnode; typedef struct Node2 //定义存储前缀表达式的结点类型 {int data; int data1; char data2; struct Node2 *next; struct Node2 *prior; }Lnode2; 3.运行、测试与分析 （1）表达式求值问题 （1）按提示输入中缀表达式，如图 1.1 所示。如输入中缀表达式不正确，提示输入有误，如图 1.2,1.3 所示。 图 1.1 图1 .2 图1 .3 （2 ）选择表达式转换并求值方式。按“1 ”选择中缀表达式求值，如图1 .4所示。 图1 .4 （3 ）按“2 ”选择中缀表达式转变为后缀表达式并求值，如图1 .5 所示。 图1 .5 （4 ）按“3 ”选择中缀表达式转变为前缀表达式并求值，如图1 .6 所示。 图1 .6 附录：源代码 （1）表达式求值问题 #include #include #define MAXNUM 100 typedef struct Node //定义存储中缀表达式的结点类型 {int data; int data1; char data2; struct Node *next; }Lnode; typedef struct Node2 //定义存储前缀表达式的结点类型 {int data; int data1; char data2; struct Node2 *next; struct Node2 *prior; }Lnode2; typedef int selemtype1; //定义运算数栈的结点 typedef struct //定义运算数栈的类型 {selemtype1 *base; selemtype1 *top; }sqstack1; void InitStack1(sqstack1 &s) /...
