下载文档原格式
表达式求值的类型定义与操作实现一、需求分析设计一个程序，演示用算符优先法对算术表达式求值的过程。
利用算符优先关系，实现对算术四则混合运算表达式的求值。
（1）输入的形式：表达式，例如2*(3+4)#；包含的运算符只能有'+' 、'-' 、'*' 、'/' 、'('、')'；（2）输出的形式：运算结果，例如Answer is:77.000000；（3）程序所能达到的功能：对表达式求值并输出结果。
二、概要设计：本课程设计需要用到抽象数据类型栈存储表达式。
本部分给出栈的类型定义与表达式求值操作描述。
1、存储结构（顺序栈）：typedef struct SqStack{SElemType *base;SElemType *top;int stacksize;}SqStack;2、基本操作：Status InitStack(SqStack &s)操作结果：初始化一个空栈s。
Status GetTop(SqStack s,SElemType &e)初始条件：栈s已存在。
操作结果：得到s的栈顶元素并用e带回。
Status Push(SqStack &s,SElemType e)初始条件：栈s已存在。
操作结果：向栈s中压入元素e。
Status Pop(SqStack &s,SElemType &e)初始条件：栈s已存在‘操作结果：弹出栈s栈顶元素，并用e带回。
Status In(char e)操作结果：判断e是否为7种运算符之一char Precede(char p,char c)操作结果：比较运算符p与运算符c的优先级。
SElemType Operate(SElemType x,char n,SElemType y)操作结果：计算x,y对运算符n的运算结果。
三、详细设计本部分主要给出表达式求值的实现算法1、初始化一个空栈sStatus 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;}2、读取栈顶元素Status GetTop(SqStack s,SElemType &e){if(s.top==s.base)return ERROR;e=*(s.top-1);return OK;}3、向栈s中压入元素eStatus Push(SqStack &s,SElemType e){if(s.top-s.base>=s.stacksize){s.base=(SElemType*)realloc(s.base,(s.stacksize+STACKINCREMENT)*sizeof(SElemType));if(!s.base)exit(OVERFLOW);s.top=s.base+s.stacksize;s.stacksize+=STACKINCREMENT;}*s.top++=e;return OK;}4、弹出栈顶元素Status Pop(SqStack &s,SElemType &e) //{if(s.top==s.base)exit(OVERFLOW);e=* --s.top;return OK;}5、判断是否为7种运算符之一Status In(char e) / /{switch(e){case '+':case '-':case '*':case '/':case '(':case ')':case '#':return(1);break;default:return(0);}}6、比较两运算符优先级char Precede(char p,char c){ 'switch(p){case '+':case '-':switch(c){case '*':case '/':case '(':return '<';break;default:return '>';break;}break;case '*':case '/':switch(c){case '(':return '<';break;default:return '>';break;}break;case '(':switch(c){case ')':return '=';break;case '#':printf("ERROR!!\n");exit(OK);default:return '<';break;}break;case ')':switch(c){case '(':printf("ERROR!!\n");exit(OK);default:return '>';break;}break;case '#':switch(c){case ')':printf("ERROR!!\n");exit(OK);case '#':return '=';break;default:return '<';break;}break;}}7、四则运算SElemType Operate(SElemType x,char n,SElemType y) {SElemType e;switch(n){case '+':e=x+y;break;case '-':e=x-y;break;case '*':e=x*y;break;case '/':if(y==0){printf("分母不能为0！\n");exit(1);}else{e=x/y;break;}}return e;}8、主函数进行表达式求值void main(){SqStack OPTR,OPND;SElemType p,s,a,b,theta;char c;printf("请输入一个表达式并以'#'结束\n(只包括' +-*/' 和'('')'):\n");InitStack(OPTR);Push(OPTR,'#');InitStack(OPND);c=getchar();GetTop(OPTR,p);while(c!='#'||p!='#'){if(!In(c)){s=c-48;c=getchar();while(c>='0'&&c<='9'){s=s*10+(c-48);c=getchar();}Push(OPND,s);}else{switch(Precede(p,c)){case '<':Push(OPTR,c);c=getchar();break;case '=':Pop(OPTR,s);c=getchar();break;case '>':Pop(OPTR,theta);Pop(OPND,b);Pop(OPND,a);Push(OPND,Operate(a,theta,b));break;}GetTop(OPTR,p);}}//whileprintf("\n\n");GetTop(OPND,p);printf("Answer is:%f\n",p);getch();}四、调试分析1、初始化了一种类型的两个栈，分别用来存放数值和运算符。
表达式求值算法总结(C++)表达式求值，一般采用栈和队列的方式来求值，下面介绍表达式求值的两种算法。
方法一、使用两个栈，一个为操作符栈OPTR(operator)，一个是操作数栈OPND(operand)算法过程：当输入3 * ( 4 - 1 * 2 ) + 6 / ( 1 + 1 )时，为简单方便，我们输入时，按照字符的顺序一个一个的处理，比如ch = getchar()。
然后根据ch 的值判断：若ch 是数字，直接压入操作数栈OPND；若ch 是'('，直接入栈OPTR;若ch 是')'，若OPTR 和OPND 非空，弹出OPTR的栈顶操作符，弹出OPND栈顶的两个操作数，做运算，然后见个结果压入栈OPND，直到弹出的OPTR栈顶元素时')';若ch 是操作符(比如+, -, *, /)，如果OPTR栈顶元素是(，直接入栈OPTR，如果不是'('且OPTR栈非空且栈顶元素操作符的优先级大于ch，那么弹出OPTR的栈顶操作符，并弹出OPND中栈顶的两个元素，做运算，将运算结果入栈OPND，此时，重复这一步操作；否则将ch入栈OPTR；若ch为EOF，说明表达式已经输入完成，判断OPTR是否为空，若非空，一次弹出OPTR 栈顶操作符，并与OPND栈顶两个元素做运算，将运算结果入栈OPND，最后表达式的结果即OPND的栈底元素。
以表达式3 * ( 4 - 1 * 2 ) + 6 / ( 1 + 1 )为例，计算过程如下所示：通过上述的计算过程，写出伪代码如下所示：void GetExpress(Stack * OPTR, Stack * OPND){char ch;while ((ch = getchar ()) != EOF) {if (IsDigit (ch)) {PushStack (OPND, ch);}else if (ch == '(')PushStack (OPTR, ch);else if (ch == ')') {while (!IsStackEmpty(OPTR)) {PopStack (OPTR, op);if (op == ')')break;PopStack (OPND, num2);PopStack (OPND, num1);res = Calc (num1, num2, op);PushStack (OPND, res);}}else if (ch == '+' || ch == '-'|| ch == '*' || ch == '/') {while (!IsStackEmpty (OPTR) && GetTop (OPTR)!='(' && GetTop (OPTR)>ch) { PopStack (OPTR, op);PopStack (OPND, num2);PopStack (OPND, num1);res = Calc (num1, num2, op);PushStack (OPND, res);}if (IsStackEmpty (OPTR) || GetTop(OPTR)=='(')PushStack (OPTR, ch);}}}// 当表达式输入完成后，需要对OPTR栈和OPND中的元素进行运算int GetValue(Stack * OPTR, Stack * OPND){while (!IsStackEmpty (OPTR)) {PopStack (OPTR, op);PopStack (OPND, num2);PopStack (OPND, num1);res = Calc (num1, num2, op);PushStack (OPND, res);}// 最后的操作数栈OPND栈顶元素即是表达式的值return GetTop(OPND);}PS: 上面没有指出表达式非法的情况方法二：采用中缀表达式的方法，求取表达式的中缀表达式，借用一个操作符栈OPTR和中缀表达式队列Queue，求取中缀表达式，然后对中缀表达式求值。
字符串表达式求值（⽀持多种类型运算符）⼀、说明1. 输⼊字符串为中缀表达式，⽆需转为后缀表达式2. ⽀持的运算符包括：算术运算符："+,-,*,/"关系运算符：">,<,>=,<=,=,!="(注意等于运算符采⽤的是⼀个等号)逻辑运算符："&&,||"3. ⽀持⼤于10的数字，不⽀持负数操作数，但⽀持中间结果和返回值为负数⼆、算法原理&步骤本⽂算法对中缀表达式形式字符串进⾏求值，同时⽀持与或运算和逻辑运算(若含有关系运算符或者逻辑运算符，则输出为1或者0)。
类似于加减乘除，将关系运算符和逻辑运算符看作优先级低的运算符进⾏处理，优先级：算术运算符>关系运算符>逻辑运算符。
步骤：1. 初始化两个空堆栈，⼀个存放操作数，⼀个存放运算符。
2. 从左⾄右扫描输⼊字符串，依次读取。
2.1 若为操作数，则压⼊操作数栈；2.2 若为运算符，判断其优先级是否⼤于运算符栈栈顶元素优先级。
若⼤于栈顶元素优先级，则直接压栈；否则，弹出栈顶元素operator，同时依次从操作数栈中弹出两个元素number1,number2，计算表达式(number2 operator number1)的值value，并将值value压⼊操作数栈。
重复上述过程直⾄当前扫描的操作符优先级⼤于栈顶元素，然后将当前运算符压栈。
3. 弹出运算符栈顶元素operator，同时依次从操作数栈中弹出两个元素number1,number2，计算表达式(number2 operator number1)的值value，并将值value压⼊操作数栈。
重复上述过程直⾄运算符栈为空。
4. 此时操作数栈应该只有⼀个元素，即为表达式的值。
三、代码&测试求值函数：1/* 字符串表达式求值2 * @param input: 输⼊的字符串3 * @param output: 表达式的值，若含有关系运算符则为1或者04 * return 计算过程是否正常5*/6bool ExpValue(string input,int& output)7 {8 stack<int> operand_stack;9 stack<string> operator_stack;1011char prev = 0; // 上⼀个属于运算符的字符12for (int i = 0; i < input.size(); i++)13 {14char c = input[i];15// prev是否是⼀个完整运算符16if (!isOperator(c) && prev)17 {18string new_op = string("").append(1, prev);19 addNewOperator(new_op, operand_stack, operator_stack);20 prev = 0;21 }2223// 数字24if (isdigit(c))25 {26int val_c = c - '0';27if (i > 0 && isdigit(input[i - 1]))28 {29int top_num = operand_stack.top();30 top_num = top_num * 10 + val_c;31 operand_stack.pop();32 operand_stack.push(top_num);33 }34else35 operand_stack.push(val_c);36 }37// 运算符字符38else if (isOperator(c))39 {40// 处理两字符运算符41if (prev)42 {43string new_op = string("").append(1, prev).append(1, c);44 addNewOperator(new_op, operand_stack, operator_stack);45 prev = 0;46 }47else48 prev = c;49 }50else if (c == '(')51 operator_stack.push("(");52else if (c == ')')53 {54// 处理括号内的运算符55while (operator_stack.top()!="(")56 {57int num1 = operand_stack.top();58 operand_stack.pop();59int num2 = operand_stack.top();60 operand_stack.pop();61string op = operator_stack.top();62 operator_stack.pop();6364int val = Calculate(num2, num1, op);65 operand_stack.push(val);66 }67 operator_stack.pop(); // 弹出"("68 }69 }70 assert(operand_stack.size() == operator_stack.size() + 1);71// 弹出所有运算符72while(!operator_stack.empty())73 {74int num2 = operand_stack.top();75 operand_stack.pop();76int num1 = operand_stack.top();77 operand_stack.pop();78string op = operator_stack.top();79 operator_stack.pop();8081int val = Calculate(num1, num2, op);82 operand_stack.push(val);83 }8485if (operand_stack.size() == 1) {86 output = operand_stack.top();87return true;88 }89return false;90 }其中⽤到的⼦函数有：/* 判断字符是否属于运算符 */bool isOperator(char c){switch (c){case'-':case'+':case'*':case'/':case'%':case'<':case'>':case'=':case'!':case'&':case'|':return true;default:return false;}}/* 获取运算符优先级 */int getPriority(string op){int temp = 0;if (op == "*" || op == "/" || op == "%")temp = 4;else if (op == "+" || op == "-")temp = 3;else if (op == ">" || op == "<" || op == ">=" || op == "<="|| op == "=" || op == "!=")temp = 2;else if (op == "&&" || op == "||")temp = 1;return temp;}/** 返回⼀个两元中缀表达式的值* syntax: num_front op num_back* @param num_front: 前操作数* @param num_back: 后操作数* @param op: 运算符*/int Calculate(int num_front, int num_back, string op){if (op == "+")return num_front + num_back;else if (op == "-")return num_front - num_back;else if (op == "*")return num_front * num_back;else if (op == "/")return num_front / num_back;else if (op == "%")return num_front % num_back;else if (op == "!=")return num_front != num_back;else if (op == ">=")return num_front >= num_back;else if (op == "<=")return num_front <= num_back;else if (op == "=")return num_front == num_back;else if (op == ">")return num_front > num_back;else if (op == "<")return num_front < num_back;else if (op == "&&")return num_front && num_back;else if (op == "||")return num_front || num_back;return0;}/* 新运算符⼊栈操作 */void addNewOperator(string new_op, stack<int>& operand_stack, stack<string>& operator_stack) {while (!operator_stack.empty() && getPriority(operator_stack.top()) >= getPriority(new_op)){int num2 = operand_stack.top();operand_stack.pop();int num1 = operand_stack.top();operand_stack.pop();string op = operator_stack.top();operator_stack.pop();int val = Calculate(num1, num2, op); operand_stack.push(val);}operator_stack.push(new_op);}View Code测试结果：int main(){string s0 = "10-1*10+3%2";string s1 = "100 + (3-33)*2";string s2 = "20+1 >= 20 && 20+1 < 20"; string s3 = "10>20 || 10/1>=5";int ret = -1;if (ExpValue(s0, ret))cout << s0 << "的值: " << ret << endl; if (ExpValue(s1, ret))cout << s1 << "的值: " << ret << endl; if (ExpValue(s2, ret))cout << s2 << "的值: " << ret << endl; if (ExpValue(s3, ret))cout << s3 << "的值: " << ret << endl; return0;}上述代码的执⾏结果为：。
表达式求值(数据结构)表达式求值(数据结构)1.引言在计算机科学中，表达式求值是一项重要的任务。
它涉及解析和计算数学或逻辑表达式，以得出最终结果。
表达式可以包括数字、变量、运算符和函数，通过采用特定的计算规则，我们可以将这些表达式转化为具体的数值或逻辑结果。
2.表达式的基本概念2.1 数字在表达式中，数字是最基本的元素。
可以是整数或浮点数，用于进行算术计算。
2.2 变量变量是用于存储和代表值的符号，它可以在表达式中使用。
变量可以通过赋值操作来获得具体的值，在表达式求值过程中，变量会被相应的数值替换。
2.3 运算符运算符是用于执行特定操作的符号。
常见的算术运算符包括加法(+), 减法(-), 乘法和除法(/）逻辑运算符包括与(&&), 或(--------) 和非(!）在表达式求值中，运算符的优先级和结合性规则是非常重要的。
2.4 函数函数是一段封装了特定功能的代码块，可以接受输入参数并返回一个结果。
在表达式中，函数可以用于处理特定的数据操作或算法。
例如，sin(x) 和cos(x) 是常见的三角函数。
3.表达式求值的步骤3.1 词法分析首先，需要对表达式进行词法分析，将表达式分解为一个个的词法单元，例如数字、变量、运算符和函数等。
词法分析可以使用正则表达式或者逐字符扫描的方式进行。
3.2 语法分析在得到词法单元序列后，需要进行语法分析，根据语法规则验证表达式的结构是否正确。
语法分析可以使用自顶向下的LL(1)分析方法或者自底向上的LR分析方法。
3.3 语义分析一旦表达式的结构验证通过，就需要进行语义分析。
语义分析的任务是根据语法树运用特定的求值规则，将表达式转换为具体的数值或逻辑结果。
在语义分析过程中，需要处理变量的赋值和函数的调用。
4.表达式求值的例子为了更好地理解表达式求值的过程，以下是一个例子：________表达式：________ 2 (3 + 4) ●5 / 24.1 词法分析：________将表达式分解为以下词法单元：________ 数字(2, 3, 4, 5), 运算符(, +, -), 括号(), 除法运算符(/)4.2 语法分析：________根据语法规则验证表达式的结构是否正确，构建语法树：________-/ \\// \\ / \\2 + 5 2/ \\3 44.3 语义分析：________根据语法树使用求值规则，依次计算每个节点的值：________●节点：________ 2 (7) ●5 / 2●节点：________ 2 7 ●5 / 2●节点：________ 14 ●5 / 2●节点：________ 14 ●2.5●最终结果：________ 11.55.附件本文档没有涉及附件。
数据结构课程设计院别计算机与通信工程学院专业计算机科学与技术班级学号姓名指导教师成绩2013 年7 月18 日目录一、设计课题 (3)二、需求分析 (3)三、算法设计 (3)四、调试分析 (9)五、用户手册 (10)六、测试结果 (10)七、附录（源代码） (13)八、参考文献 (21)一、设计课题： 表达式求值 二、需求分析：当用户输入一个合法的算术表达式后，能够返回正确的结果。
能够计算的运算符包括：加、减、乘、除、括号；能够计算的操作数要求在实数范围内；对于异常表达式能给出错误提示。
三、算法设计：概要说明：为实现上述程序功能，1. 首先置操作数栈为空栈，表达式起始符＃为运算符栈的栈底元素；2. 依次扫描表达式中每个字符，若是操作数则进OPND 栈；若是运算符，则和OPTR 栈的栈顶运算符比较优先权后作相应操作，直至整个表达式求值完毕。
3. 先做一个适合个位的+-*/运算, 其次就要考虑到对n 位和小数点的运算。
模块间调用关系：调用主程序模块————>输出模块详细说明（ADT 描述） ：ADT SqStack{数据对象：D={i a |i a ∈ElemSet,i=1,2,…，n, n ≧0} 数据对象：R1={<1,-i i a a >|1-i a ,D a i ∈,i=2,…，n}约定n a 端为栈顶，i a 端为栈底。
基本操作：InitStack(&S)操作结果：构造一个空栈S 。
GetTop(S)初始条件：栈S 已存在。
操作结果：用P 返回S 的栈顶元素。
Push(&S ，e)初始条件：栈S 已存在。
操作结果：插入元素ch 为新的栈顶元素。
Pop(&S ，e)初始条件：栈S 已存在。
操作结果：删除S 的栈顶元素。
In(c)操作结果：判断字符是否是运算符，运算符即返回1。
Precede(c1, c2)初始条件：c1,c2为运算符。
操作结果：判断运算符优先权，返回优先权高的。
表达式求值算法表达式求值算法是计算机科学中的重要概念之一，用于计算数学表达式的结果。
在编程语言中，表达式求值是一项基本的操作，并且经常在计算过程中需要用到。
本文将介绍一些常见的表达式求值算法及其实现。
1. 逆波兰表达式法逆波兰表达式法是一种用于计算数学表达式的算法，它使用后缀表达式（也称为逆波兰表达式）来表示表达式。
逆波兰表达式是将操作符放在操作数之后的一种表示方法。
对于任意一个数学表达式，都可以通过将中缀表达式转换为后缀表达式，然后使用栈结构计算得到结果。
逆波兰表达式法的优点是计算顺序明确，不需要考虑运算符的优先级和括号的处理。
2. 中缀表达式转后缀表达式法中缀表达式是我们常见的数学表达式，如 3 + 4 * 5。
在中缀表达式中，操作符的优先级和括号起着很大的作用。
为了将中缀表达式转换为后缀表达式，我们需要使用到栈结构。
具体的算法如下：- 遍历中缀表达式的每个元素。
- 如果是操作数，则直接输出。
- 如果是操作符，则判断其与栈顶操作符的优先级，决定是否将其压入栈。
- 如果是左括号，则直接压入栈。
- 如果是右括号，则依次弹出栈顶操作符，并输出，直到遇到左括号为止。
- 遍历完表达式后，如果栈不为空，则依次弹出栈顶操作符，并输出。
3. 后缀表达式求值法后缀表达式（逆波兰表达式）的求值方法相对简单。
我们可以使用栈结构来计算后缀表达式的结果。
具体的算法如下：- 遍历后缀表达式的每个元素。
- 如果是操作数，则将其压入栈。
- 如果是操作符，则弹出栈顶的两个操作数，执行相应的计算，并将结果压入栈。
- 遍历完后缀表达式后，栈中最后剩下的元素即为计算结果。
4. 二叉树表示法除了逆波兰表达式法和中缀表达式法，我们还可以使用二叉树来表示表达式，并通过遍历二叉树来计算表达式的结果。
具体的算法如下：- 构建二叉树，将表达式的操作符作为根节点，将操作数作为叶节点。
- 通过后序遍历二叉树，计算出每个子树的值，并将结果返回给其父节点。
实验一：算术表达式求值问题题目：编制一个利用栈求解算数表达式的程序班级：姓名：学号：完成日期：一.需求分析1.问题描述：表达式计算是实现程序设计语言的基本问题之一，也是栈的应用的一个典型的例子2．基本要求：以字符序列的形式从终端输入语法正确的、不含变量的整数表达式。
利用教科书表3.1给出的算符优先关系，可以使用两个栈，一个用以寄存运算符，另一个用以寄存操作数和运算结果。
实现对算术四则混合运算表达式的求值，并仿照教科书的例3-1的演示在求值中实现运算符栈、运算数栈、输入字符和主要操作的变化过程。
3.演示程序：是用户在计算机终端进行输入而执行操作。
4.执行程序：本程序为了使用具体，采用列表式的方式来完成程序的演示，只需按提示输入表达式即可。
(输入时以指定字符结束，否则出错！)5.测试数据：教科书例3-1的算术表达式3*(7-2),，以及下列表达式8；1+2+3+4 ；2*(6+2*(3+6*(6+6)))；(((6+6)*6+3)*2+6)*2；二.概要设计1.任意两个相继出现的算符θ1和θ2之间的优先关系至多是下列3种关系之一：2.为实现上述功能，应建立两个栈，一个是运算符栈，另一个是运算数栈。
为此，需要有一个栈的抽象数据类型。
该栈的抽象数据类型定义为：ADT Stack{数据对象：D={a i| a i∈ElemSet,i=1,2,3……，n,n≥0}数据关系：R1={<a i-1,a i>| a i-1,a i∈D,i=1,2,3,……，n}约定其中a i端为栈底，a n端为栈顶。
基本操作：(1.)对运算符栈的基本操作：void InitStack1(Stack1 &S1); //声明栈建立函数操作结果：构造一个空栈(运算符栈)void Push1(Stack1 &S1,char e); //声明入栈函数初始条件：运算符栈S1已存在操作结果：插入字符元素e为新的栈顶元素char GetTop1(Stack1 &S1); //声明取栈顶元素函数初始条件：运算符栈S1已存在且非空操作结果：返回栈S1的栈顶元素char Pop1(Stack1 &S1); //声明出栈函数初始条件：运算符栈S1已存在操作结果：删除S1的栈顶元素，并用e返回其值void ShowStack1(Stack1 &S1); //从栈底到栈顶依次输出各元素初始条件：栈S1存在且不为空操作结果：从栈底到栈顶依次输出各元素(2.)对运算数栈的基本操作：void InitStack2(Stack2 &S2); //声明栈建立函数操作结果：构造一个空栈(运算数栈)void Push2(Stack2 &S2,float e); //声明入压栈函数初始条件：运算数栈S2已存在操作条件：插入浮点型元素e为新的栈顶元素float GetTop2(Stack2 &S2); //声明取栈顶元素函数初始条件：运算数栈S2已存在操作结果：用e返回栈S2的栈顶元素float Pop2(Stack2 &S2); //声明出栈函数初始条件：运算数栈S2已存在操作结果：删除S2的栈顶元素，并用e返回其值void ShowStack2(Stack2 &S2); //从栈底到栈顶依次输出各元素初始条件：栈S2存在且不为空操作结果：从栈底到栈顶依次输出各元素(3.)对表达式的基本操作：void evaluate(Stack1 &S1,Stack2 &S2); //确定如何入栈函数初始条件：栈S1和S2已存在操作结果：实现字符的入栈操作char Compare(char m,char n); //声明比较函数操作结果：比较运算符的优先级float Operate(float a,char ch,float b); //声明运算函数操作结果：实现表达式的运算}ADT Stack3.此抽象数据类型中的一些常量如下：#define STACK_INIT_SIZE 100#define STACKINCREMENT 104.栈结构体的定义如下所示：typedef struct //运算符栈{char *base;char *top;int stacksize;}Stack1;typedef struct //运算数栈{float *base;float *top;int stacksize;}Stack2;5.本程序包含三个模块1).主程序模块void main( ){初始化；调用函数；函数实现；}2).栈模块——实现栈中的抽象数据类型3).表达式求值模块——实现表达式的求值操作各模块之间的调用关系如下：主程序模块栈模块表达式求值模块6.表达式求值入栈及出栈的伪码算法：表达式求值(开始){将‘#’入栈，作为低级运算符输入不含变量的表达式（以#结束!）如果c!='#'||GetTop1(S1)!='#'如果输入的字符如果不是运算符号，则继续输入直到输入的是运算符为止，将非运算符转换成浮点数如果输入的是运算符遇到运算符，则将之前输入的操作数进栈比较运算符的优先级栈顶元素优先级低，则入栈且继续输入栈顶元素优先级相等，脱括号并接收下一字符栈顶元素优先级高，则退栈并将运算结果入栈显示表达式最终结果}//结束三.详细设计// 表达式求值.cpp : Defines the entry point for the console application.//#include "stdafx.h"#include<iostream>using namespace std;#define STACK_INIT_SIZE 100#define STACKINCREMENT 10typedef struct //运算符栈{char *base;char *top;int stacksize;}Stack1;typedef struct //运算数栈{float *base;float *top;int stacksize;}Stack2;/*************************************************************函数的申明*************************************************************/void InitStack1(Stack1 &S1); //声明栈建立函数void InitStack2(Stack2 &S2); //声明栈建立函数void Push1(Stack1 &S1,char e); //声明入栈函数void Push2(Stack2 &S2,float e); //声明入压栈函数char GetTop1(Stack1 &S1); //声明取栈顶元素函数float GetTop2(Stack2 &S2); //声明取栈顶元素函数char Pop1(Stack1 &S1); //声明出栈函数float Pop2(Stack2 &S2); //声明出栈函数void evaluate(Stack1 &S1,Stack2 &S2);//确定如何入栈函数char Compare(char m,char n); //声明比较函数float Operate(float a,char ch,float b);//声明运算函数void ShowStack1(Stack1 &S1); //从栈底到栈顶依次输出各元素void ShowStack2(Stack2 &S2); //从栈底到栈顶依次输出各元素/*************************************************************运算符栈函数的定义*************************************************************/void InitStack1(Stack1 &S1)//构造一个空栈S1{S1.base=(char *)malloc(STACK_INIT_SIZE *sizeof(char));if(!S1.base)cout<<"存储分配失败！";//存储分配失败S1.top=S1.base;S1.stacksize=STACK_INIT_SIZE;}void Push1(Stack1 &S1,char e)//入栈{if(S1.top-S1.base>=S1.stacksize)//如果栈满，追加存储空间{S1.base=(char *)realloc(S1.base,(S1.stacksize+STACKINCREMENT)*sizeof(char));if(!S1.base)cout<<"存储分配失败！";else{S1.top=S1.base+S1.stacksize;S1.stacksize+=STACKINCREMENT;。
