简单的表达式求值

一、设计思想算数四则运算的规则为：①对带括号的操作执行顺序为，先括号里面的，后括号外面的。

如遇多层括号，则按从最内层依序至外的操作运算。

②先乘除后加减③优先级相同的操作符按操作符先后顺序从左到右依次计算。

算数表达式由数值和操作符（+、-、*、/、%、（、））构成，然而开始输入表达式全是字符构成，因此出现一个问题，将算数字符表达式中的数字字符转化为浮点型数值再进行运算。

中缀表达式求值算法基本思路：1.建立两个栈，一个用来存数字，一个用来存操作符。

2.依次扫描表达式字符，如果是数字字符，将其转化为浮点数，直接存入数值栈。

3.如果是操作符，观察操作符，判断其与符号栈栈顶操作符的优先级，如果栈顶元素优先级低于观察字符，就入栈。

4.如果栈顶元素的优先级高于观察字符，就从数值栈中取出两个操作数，从符号栈中取出栈顶操作符，进行运算，将运算结果存入数值栈。

5.重复操作，直到操作符栈顶元素优先级低于观察字符，此时操作符入栈。

6.然后对下一个字符进行扫描，如果是‘（’，直接入栈，如果是‘）’，则从数值栈中取两个操作数，符号栈中取出一个操作符，然后进行计算后得数放入数值栈中。

7.不断进行此类操作，直到从栈中取出的是左括号为止，左括号去掉，扫描下一个。

扫描结束后，计算也结束了，计算的结果就存放在数值栈中。

8.最后把数值栈中的数取出，就是所得的计算结果。

中缀表达式转化为后缀表达式求值基本思路：中缀式转化为后缀式：1.创建一个操作符栈和一个字符串数组，数组用来存放转化的后缀表达式。

2.对输入的表达式字符串进行逐个扫描，如果是数字或者小数点，就直接存放在数组中，如果扫描过程中遇到不为数字或小数点字符就在后面加上一个空格作为分隔标志。

3.如果是操作符就和符号栈中已有的操作符比较，如果比栈中的操作符优先级高，则直接入栈。

4.否则符号栈中元素出栈，存到字符串数组中，然后再次观察栈顶，直到栈中元素优先级低于扫描的操作符，则此被扫描操作符入栈。

C#算术表达式求值（后缀法），看这⼀篇就够了⼀、种类介绍算术表达式有三种：前缀表达式、中缀表达式和后缀表达式。

⼀般⽤的是中缀，⽐如1+1，前后缀就是把操作符移到前⾯和后⾯，下⾯简单介绍⼀下这三种表达式。

1、前缀表⽰法前缀表⽰法⼜叫波兰表⽰法，他的操作符置于操作数的前⾯（例：+ 1 2），是波兰数学家扬·武卡谢维奇1920年代引⼊的，⽤于简化命题逻辑。

因为我们⼀般认为操作符是在操作数中间的，所以在⽇常⽣活中⽤的不多，但在计算机科学领域占有⼀席之地。

⼀般的表⽰法对计算机来说处理很⿇烦，每个符号都要考虑优先级，还有括号这种会打乱优先级的存在，将使计算机花费⼤量的资源进⾏解析。

⽽前缀表⽰法没有优先级的概念，他是按顺序处理的。

举个例⼦：9-2*3这个式⼦，计算机需要先分析优先级，先乘后减，找到2*3，再进⾏减操作；化成前缀表⽰法就是：- 9 * 2 3，计算机可以依次读取，操作符作⽤于后⼀个操作数，遇到减就是让9减去后⾯的数，⽽跟着9的是乘，也就是说让9减去乘的结果，这对计算机来说很简单，按顺序来就⾏了。

2、中缀表⽰法这也就是我们⼀般的表⽰法，他的操作符置于操作数的中间（例：1 + 2），前⾯也说过这种⽅法不容易被计算机解析，但他符合⼈们的普遍⽤法，许多编程语⾔也就⽤这种⽅法了。

在中缀表⽰法中括号是必须有的，要不然运算顺序会乱掉。

3、后缀表⽰法后缀表⽰法⼜叫逆波兰表⽰法，他的操作符置于操作数的后⾯（例：1 2 +），他和前缀表⽰法都对计算机⽐较友好，但他很容易⽤堆栈解析，所以在计算机中⽤的很多。

他的解释过程⼀般是：操作数⼊栈；遇到操作符时，操作数出栈，求值，将结果⼊栈；当⼀遍后，栈顶就是表达式的值。

因此逆波兰表达式的求值使⽤堆栈结构很容易实现，且能很快求值。

注意：逆波兰记法并不是简单的波兰表达式的反转。

因为对于不满⾜交换律的操作符，它的操作数写法仍然是常规顺序，如，波兰记法/ 6 3的逆波兰记法是6 3 /⽽不是3 6 /；数字的数位写法也是常规顺序。

Openjudge-NOI题库-简单算术表达式求值题⽬描述 Description两位正整数的简单算术运算（只考虑整数运算），算术运算为：+，加法运算；-，减法运算；*，乘法运算；/，整除运算；%，取余运算。

算术表达式的格式为（运算符前后可能有空格）：运算数运算符运算数请输出相应的结果。

输⼊输出格式 Input/output输⼊：⼀⾏算术表达式。

输出：整型算数运算的结果（结果值不⼀定为2位数，可能多于2位或少于2位）。

输⼊输出样例 Sample input/output样例测试点#1输⼊样例：32+64输出样例：96思路：可以先⽤⼀个字符串存⼊这个表达式，分别从前往后，从后往前找数字，从前往后遍历这个数组，在后⾯⼀个字符不为空格的情况下，变为数字，从后往前遍历这个数组，在前⾯⼀个字符不为空格情况下，变为数字，然后再扫描⼀遍这个数组看看是什么运算符号，最后判断运算符号输出结果即可。

代码如下：1 #include <stdio.h>2 #include <string.h>3int main()4 {5int n,i;6char a[200];7int f=0,l=0;8 gets(a);9for(i=0;i<strlen(a);i++)//⾸个两位数10 {11if(a[i]>='0'&&a[i]<='9')//如果是数字12 {13if(a[i+1]>='0'&&a[i+1]<='9')//如果后⾯那个也是数字14 {15 f=(f+a[i]-48)*10;//变为数字往前进⼀位16 }17else//否则是空格什么的直接存为数字18 {19 f=f+a[i]-48;20break;21 }22 }23 }24for(i=strlen(a);i>0;i--)//第⼆个两位数25 {26if(a[i]>='0'&&a[i]<='9')//如果是数字27 {28if(a[i-1]>='0'&&a[i-1]<='9')//如果前⾯那个也是数字29 {30 l=l+a[i]-48;31 }32else//否则是空格什么的直接存为数字33 {34 l=l+(a[i]-48)*10;//变为数字往前进⼀位35break;36 } /* 35+14 */37 }38 }39for(i=0;i<strlen(a);i++)40 {41if(a[i]=='+') printf("%d\n",f+l);42else if(a[i]=='-') printf("%d\n",f-l);43else if(a[i]=='*') printf("%d\n",f*l);44else if(a[i]=='/') printf("%d\n",f/l); 45else if(a[i]=='%') printf("%d\n",f%l);46 }47return0;48 }。

表达式求值算法表达式求值算法是计算机科学中的重要概念之一，用于计算数学表达式的结果。

在编程语言中，表达式求值是一项基本的操作，并且经常在计算过程中需要用到。

本文将介绍一些常见的表达式求值算法及其实现。

1. 逆波兰表达式法逆波兰表达式法是一种用于计算数学表达式的算法，它使用后缀表达式（也称为逆波兰表达式）来表示表达式。

逆波兰表达式是将操作符放在操作数之后的一种表示方法。

对于任意一个数学表达式，都可以通过将中缀表达式转换为后缀表达式，然后使用栈结构计算得到结果。

逆波兰表达式法的优点是计算顺序明确，不需要考虑运算符的优先级和括号的处理。

2. 中缀表达式转后缀表达式法中缀表达式是我们常见的数学表达式，如 3 + 4 * 5。

在中缀表达式中，操作符的优先级和括号起着很大的作用。

为了将中缀表达式转换为后缀表达式，我们需要使用到栈结构。

具体的算法如下：- 遍历中缀表达式的每个元素。

- 如果是操作数，则直接输出。

- 如果是操作符，则判断其与栈顶操作符的优先级，决定是否将其压入栈。

- 如果是左括号，则直接压入栈。

- 如果是右括号，则依次弹出栈顶操作符，并输出，直到遇到左括号为止。

- 遍历完表达式后，如果栈不为空，则依次弹出栈顶操作符，并输出。

3. 后缀表达式求值法后缀表达式（逆波兰表达式）的求值方法相对简单。

我们可以使用栈结构来计算后缀表达式的结果。

具体的算法如下：- 遍历后缀表达式的每个元素。

- 如果是操作数，则将其压入栈。

- 如果是操作符，则弹出栈顶的两个操作数，执行相应的计算，并将结果压入栈。

- 遍历完后缀表达式后，栈中最后剩下的元素即为计算结果。

4. 二叉树表示法除了逆波兰表达式法和中缀表达式法，我们还可以使用二叉树来表示表达式，并通过遍历二叉树来计算表达式的结果。

具体的算法如下：- 构建二叉树，将表达式的操作符作为根节点，将操作数作为叶节点。

- 通过后序遍历二叉树，计算出每个子树的值，并将结果返回给其父节点。

shell脚本四种数值计算方式在shell脚本中，可以使用四种不同的计算方式来进行数值计算：表达式求值、命令替换、算术运算和高级数学函数。

1.表达式求值：表达式求值是最简单的一种计算方式，只需要将数学表达式放在$(())中。

例如：```result=$(( 5 + 3 ))echo $result```在这个例子中，表达式求值计算了5 + 3，并将结果赋给变量result。

然后，使用echo命令打印出了结果。

2.命令替换：命令替换是一种在数学计算中使用shell命令的方式。

通过将命令放在$(中，shell会先执行该命令，然后将命令的输出结果作为数值计算的一部分。

例如：```result=$(expr 5 + 3)echo $result```在这个例子中，命令替换使用了expr命令来计算5 + 3的结果，并将结果赋给变量result。

然后，使用echo命令打印出了结果。

3.算术运算：除了使用$(( ))和$(进行计算，shell还提供了一些算术运算符来进行数值计算。

例如：```result=`expr 5 + 3`echo $result```在这个例子中，使用了expr命令和反引号(``)来执行数学计算。

结果与前两种方式相同。

4.高级数学函数：在shell脚本中，可以使用数学函数来执行更复杂的数值计算。

有一些内置的数学函数，如sqrt、sin、cos等，可以通过shell的数学库调用。

例如：```result=$(echo "sqrt(4)" ， bc -l)echo $result```在这个例子中，先使用echo命令将数学表达式"sqrt(4)"输出给bc 命令，bc命令会执行计算并将结果输出。

然后，命令替换将结果赋给变量result，并使用echo命令打印出了结果。

总结：以上是四种常用的shell脚本中进行数值计算的方式。

表达式求值、命令替换和算术运算是最常见的方式，适合于简单的数学计算。

栈的应⽤——表达式求值 表达式求值是程序设计语⾔编译中的⼀个基本问题，它的实现就是对“栈”的典型应⽤。

本⽂针对表达式求值使⽤的是最简单直观的算法“算符优先法”。

本⽂给出两种⽅式来实现表达式求值，⽅式⼀直接利⽤中缀表达式求值，需要⽤到两个栈，操作数栈和操作符栈。

⾸先置操作数栈为空栈，操作符栈仅有“#”⼀个元素。

依次读⼊表达式中的每个字符，若是操作数则进操作数栈，若是操作符则和操作符栈的栈顶运算符⽐较优先权作相应操作，直⾄整个表达式求值完毕。

⽅式⼆⾸先把中缀表达式转换为后缀表达式并存储起来，然后利⽤读出的后缀表达式完成求值，其本质上是⽅式⼀的分解过程。

表达式求值的代码如下：#include <iostream>#include "stack"#include "map"using namespace std;/* 只能求⼀位整数的加减乘除混合运算 */map<char, pair<int, int>> priority; // 存放各个操作符的栈内栈外优先级,first是栈内,second是栈外char infix[50]; // 存放初始的中缀表达式char postfix[50]; // 存放转化的后缀表达式int result;void MakePriority() // 构造运算符优先级表{priority.insert(make_pair('#', make_pair(0, 0))); // isp(#)=0, icp(#)=0priority.insert(make_pair('\n', make_pair(0, 0))); // isp(\n)=0, icp(\n)=0 表达式结尾的'#'⽤'\n'代替,这样可以省略表达式末尾的结束符'#'priority.insert(make_pair('(', make_pair(1, 6))); // isp(()=1, icp(()=6priority.insert(make_pair('*', make_pair(5, 4))); // isp(*)=5, icp(*)=4priority.insert(make_pair('/', make_pair(5, 4))); // isp(/)=5, icp(/)=4priority.insert(make_pair('%', make_pair(5, 4))); // isp(%)=5, icp(%)=4priority.insert(make_pair('+', make_pair(3, 2))); // isp(+)=3, icp(+)=2priority.insert(make_pair('-', make_pair(3, 2))); // isp(-)=3, icp(-)=2priority.insert(make_pair(')', make_pair(6, 1))); // isp())=6, icp())=1}void InfixToPostfix() // 把中缀表达式转换为后缀表达式{int i = 0;stack<char> optrStack; // 操作符栈char optr; // optr为栈顶的操作符optrStack.push('#');while (!optrStack.empty()){if (isdigit(infix[i])) // 是操作数则直接输出(追加到postfix结尾){postfix[strlen(postfix)] = infix[i];postfix[strlen(postfix) + 1] = '\0';i++; // 读⼊中缀表达式的下⼀个字符}else// 是操作符, ⽐较优先级{optr = optrStack.top(); // 取出栈顶操作符if (priority[infix[i]].second > priority[optr].first) // icp(infix[i]) > isp(optr),infix[i]⼊栈{optrStack.push(infix[i]);i++;}else if (priority[infix[i]].second < priority[optr].first)// icp(infix[i]) < isp(optr),optr退栈并输出{postfix[strlen(postfix)] = optr;postfix[strlen(postfix) + 1] = '\0';optrStack.pop();}else// icp(infix[i]) = isp(optr),退栈但不输出,若退出的是'(',则继续读⼊下⼀个字符{optrStack.pop();if (optr == '(')i++;}}}}void CalculateByPostfix() // 通过后缀表达式求值{int i = 0;stack<int> opndStack; // 操作数栈int left, right; // 左右操作数int value; // 中间结果int newOpnd;while (postfix[i] != '#' && i < strlen(postfix)){switch (postfix[i]){case'+':right = opndStack.top(); // 从操作数栈中取出两个操作数opndStack.pop();left = opndStack.top();opndStack.pop();value = left + right;opndStack.push(value); // 中间结果⼊栈break;case'-':right = opndStack.top();opndStack.pop();left = opndStack.top();opndStack.pop();value = left - right;opndStack.push(value);break;case'*':right = opndStack.top();opndStack.pop();left = opndStack.top();opndStack.pop();value = left * right;opndStack.push(value);break;case'/':right = opndStack.top();opndStack.pop();left = opndStack.top();opndStack.pop();if (right == 0){cerr << "Divide by 0!" << endl;}else{value = left / right;opndStack.push(value);}break;default:newOpnd = (int)(postfix[i] - 48); // 操作数直接⼊栈opndStack.push(newOpnd);break;}i++;}result = opndStack.top();}void CalculateByInfix() // 直接利⽤中缀表达式求值{int i = 0;stack<char> optrStack; // 操作符栈stack<int> opndStack; // 操作数栈char optr; // optr为操作符栈顶的操作符int left, right, value; // 左右操作数以及中间结果optrStack.push('#');optr = optrStack.top();while (!optrStack.empty()) // 直到操作符栈为空{if (isdigit(infix[i])) // 是操作数, 进操作数栈{value = (int)(infix[i] - 48);opndStack.push(value);i++;}else// 是操作符, ⽐较优先级{optr = optrStack.top(); // 取出操作符栈顶的操作符if (priority[infix[i]].second > priority[optr].first) // icp(infix[i]) > isp(optr),infix[i]⼊栈 {optrStack.push(infix[i]);i++;}else if (priority[infix[i]].second < priority[optr].first) // icp(infix[i]) < isp(optr),optr退栈并输出{optrStack.pop();right = opndStack.top(); // 从操作数栈中取出两个操作数opndStack.pop();left = opndStack.top();opndStack.pop();switch (optr){case'+':value = left + right;opndStack.push(value); // 中间结果⼊栈break;case'-':value = left - right;opndStack.push(value); // 中间结果⼊栈break;case'*':value = left * right;opndStack.push(value); // 中间结果⼊栈break;case'/':if (right == 0){cerr << "Divide by 0!" << endl;}else{value = left / right;opndStack.push(value);}break;default:break;}}else{optrStack.pop();if (optr == '(')i++;}}}result = opndStack.top();}int main(){MakePriority(); // 构造运算符优先级表cout << "请输⼊中缀表达式：";cin >> infix;cout << "直接利⽤中缀表达式求值为：";CalculateByInfix();cout << result << endl;cout << "转化为后缀表达式：";InfixToPostfix();for (int i = 0;i < strlen(postfix);i++){cout << postfix[i];}cout << endl;cout << "利⽤后缀表达式求值为：";CalculateByPostfix();cout << result << endl;return0;} 为了⽅便起见，本⽂只是简单的设计了⼀个针对⼀位整数的四则运算进⾏求值的算法，对于处理多位整数的四则运算，需要对本⽂接受输⼊的数据类型进⾏“升阶”，把字符数组换成字符串数组，将⼀个整数的多位数字存⼊⼀个字符串进⾏处理。

一、概述二、算术表达式的二叉树表示1. 什么是二叉树2. 算术表达式的二叉树表示方法三、算术表达式二叉树的构建1. 中缀表达式转换为后缀表达式2. 后缀表达式构建二叉树四、算术表达式二叉树的求值五、应用举例六、总结一、概述在数学和计算机科学中，处理算术表达式是一个常见的问题。

在计算机中，算术表达式通常以中缀、前缀或后缀的形式出现，其中中缀表达式最为常见。

而采用二叉树来表示和求解算术表达式，是一种常见且高效的方法。

二、算术表达式的二叉树表示1. 什么是二叉树二叉树是一种树形数据结构，它的每个节点最多只能有两个子节点，分别是左子节点和右子节点。

二叉树可以为空，也可以是非空的。

2. 算术表达式的二叉树表示方法在二叉树中，每个节点要么是操作符，要么是操作数。

操作符节点的左子节点和右子节点分别表示运算符的两个操作数，而操作数节点则不包含任何子节点。

通过这种方式，可以将算术表达式表示为一个二叉树结构。

三、算术表达式二叉树的构建1. 中缀表达式转换为后缀表达式为了构建算术表达式的二叉树，首先需要将中缀表达式转换为后缀表达式。

中缀表达式是人们常见的形式，例如"2 + 3 * 5"，而后缀表达式则更适合计算机处理，例如"2 3 5 * +"。

将中缀转后缀的算法即为中缀表达式的后缀转换法则。

2. 后缀表达式构建二叉树构建二叉树的过程通常采用栈来辅助完成。

从左到右扫描后缀表达式，对于每个元素，如果是操作数，则入栈；如果是操作符，则弹出栈顶两个元素作为其左右子节点，然后将操作符节点入栈。

最终栈中只剩一个节点，即为构建的二叉树的根节点。

四、算术表达式二叉树的求值算术表达式二叉树的求值是递归进行的。

对于二叉树的每个节点，如果是操作符节点，则递归求解其左右子节点的值，并进行相应的操作；如果是操作数节点，则直接返回其值。

最终得到根节点的值，即为整个算术表达式的值。

五、应用举例以中缀表达式"2 + 3 * 5"为例，首先将其转换为后缀表达式"2 3 5 * +"，然后根据后缀表达式构建二叉树，最终求得二叉树的根节点即为算术表达式的值。

表达式求值表达式求值问题①问题描述表达式是数据运算的基本形式。

⼈们的书写习惯是中缀式，如：11+22*(7-4)/3。

中缀式的计算按运算符的优先级及括号优先的原则，相同级别从左到右进⾏计算。

表达式还有后缀式（如：22 7 4 - * 3 / 11 +）和前缀式（如：+ 11 / * 22 – 7 4 3）。

后缀表达式和前缀表达式中没有括号，给计算带来⽅便。

如后缀式计算时按运算符出现的先后进⾏计算。

本设计的主要任务是进⾏表达式形式的转换及不同形式的表达式计算。

②基本要求l 从⽂件或键盘读⼊中缀表达式。

l 设计操作数为多位整数，操作符为加、减、乘、除、求模的中缀表达式求值算法。

l 设计将中缀表达式转换为后缀表达式的算法。

l 设计将中缀表达式转换为前缀表达式的算法。

l 设计后缀表达式求值算法。

l 设计前缀表达式求值算法。

l 输出各种形式的表达式。

③设计要点提⽰l 算数表达式的计算往往是通过栈来实现的。

l 读⼊或扫描表达式的同时，完成运算符和操作数的识别处理。

l 识别操作数时，注意将其字符序列转换成整数（如：‘15’→15）或实数（如：‘15.4’ →15.4）形式进⾏存储。

l 可以将表达式转换成⼀棵⼆叉树，通过先序、中序、后序遍历得到前缀、中缀、后缀表达式。

l 仿表1来构建测试⽤例。

表1 表达式计算测试⽤例⽰例测试项⽬测试⽤例预期结果基本测试33 1+2*3-4/2511+2233 1+22*(5-3)/412 (((2)))-3-1…容错测试1+2（表达式出错提⽰2/0表达式出错提⽰2%0表达式出错提⽰(2-4)Ù3.1表达式出错提⽰2+3)(-5表达式出错提⽰(((2))-3表达式出错提⽰2.5%2表达式出错提⽰1+++1表达式出错提⽰2 2表达式出错提⽰1#1表达式出错提⽰…表达式出错提⽰1 #include <iostream>2 #include<string.h>3 #include<ctype.h>4 #include<malloc.h> /* malloc()等 */5 #include<limits.h> /* INT_MAX等 */6 #include<stdio.h> /* EOF(=^Z或F6),NULL */7 #include<stdlib.h> /* atoi() */8 #include<io.h> /* eof() */9 #include<math.h> /* floor(),ceil(),abs() */10 #include<process.h> /* exit() */11/* 函数结果状态代码 */12#define TRUE 113#define FALSE 014#define OK 115#define ERROR 016#define INFEASIBLE -117#define OVERFLOW 318/* #define OVERFLOW -2 因为在math.h中已定义OVERFLOW的值为3,故去掉此⾏ */19 typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */20 typedef int Boolean; /* Boolean是布尔类型,其值是TRUE或FALSE */21using namespace std;22 typedef char SElemType;23#define STACK_INIT_SIZE 100 //存储空间初始分配量24#define STACKINCREMENT 10//存储空间分配增量252627/*——————————————————————————栈的操作——————————————————————————*/28 typedef struct{29 SElemType * base;//在栈构造之前和销毁之后，base的值为NULL30 SElemType * top;//栈顶指针31int stacksize;32 }SqStack;33 Status InitStack(SqStack &S)34 {//构造⼀个空栈35 S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));36if(!S.base) exit(OVERFLOW);37 S.top=S.base;38 S.stacksize=STACK_INIT_SIZE;39return OK;40 }41 Status DestroyStack(SqStack &S)42 {//销毁栈43free(S.base);44 S.top=NULL;45 S.base=NULL;46 S.stacksize=0;47return OK;48 }4950 Status StackEmpty(SqStack S)51 {52if(S.top==S.base) return TRUE;53else return FALSE;54 }55int StackLength(SqStack S)56 {57return S.top-S.base;58 }59 Status GetTop(SqStack S,SElemType &e)60 {61if(S.top>S.base)62 {e=*(S.top-1);return OK;}63else return ERROR;64 }65 Status Push(SqStack &S,SElemType e)66 {67if(S.top-S.base==S.stacksize)//若栈满，追加存储空间68 {69 S.base=(SElemType *) realloc (S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));70if(!S.base) exit(OVERFLOW);//存储内存分配失败71 S.top=S.base+S.stacksize;72 S.stacksize += STACKINCREMENT;73 }74 *(S.top)=e;//可直接使⽤ *S.top++=e；75 S.top++;76return OK;77 }7879 Status Pop(SqStack &S,SElemType &e)80 {81if(S.top==S.base)82 {83 cout<<"表达式错误，溢出！！"<<endl;84 exit(OVERFLOW);85 }86 e=*--S.top;87return OK;88 }89 Status StackTraverse(SqStack S, void(* visit)(SElemType))90 {91while(S.top>S.base)92 visit(*S.base++);93 printf("\n");94return OK;95 }969798//表达式求值99char Precede(SElemType c1,SElemType c2)//判断c1,c2的优先关系,栈顶元素是c1，如果要⼊栈的元素c2优先权⼩（>），100//则弹出c1进⾏运算,再把c2继续尝试⼊栈,c1栈底，c2⼊栈运算符101 {102char f;103switch(c2)104 {105case'.' : f='<';106break;107case'+' :108case'-' : if(c1=='('||c1=='\n') f='<';109else f='>';110break;111112case'*' :113case'/' : if(c1=='*'||c1=='/'||c1==')') f='>';114else f='<';115break;116case'(' : if(c1==')')117 {118 printf("括号输⼊不合法！");119 exit(ERROR);120 }121else f='<';122break;123case')' : switch(c1)124 {125case'\n':126 printf("缺乏左括号！");127 exit(ERROR);128case'(': f='=';129break;130default : f='>';131 }132break;133case'\n' : switch(c1)134 {135case'\n': f='=';136break;137case'(':138 printf("缺少右括号！");139 exit(ERROR);140default : f='>';141 }142 }143return f;144 }145 Status In(SElemType c)146 { // 判断c是否为7种运算符之⼀147switch(c)148 {149case'.' :150case'+' :151case'-' :152case'*' :153case'/' :154case'(' :155case')' :156case'\n' :return TRUE;157default :return FALSE;158 }159 }160 SElemType Operate(SElemType a,SElemType theta,SElemType b)161 { // 做四则运算a theta b，返回运算结果162switch(theta)163 {164case'+':return a+b;165case'-':return a-b;166case'*':return a*b;167case'.':return a;168 }169if(b!=0) return a/b;170else171 {172 cout<<"分母不能为0！"<<endl;173 exit(OVERFLOW);174 }175 }176 SElemType EvaluateExpression(SElemType M[100])177 {//算术表达式求值的算符优先算法。