算术表达式的计算
在计算机中进行算术表达式的计算是通过栈来实现的。这一节首先讨论算术表达式的两种表示方法，即中缀表示法和后缀表示法，接着讨论后缀表达式求值的算法，最后讨论中缀表达式转换为后缀表达式的算法。
1. 算术表达式的两种表示
通常书写的算术表达式是由操作数(又叫运算对象或运算量)和运算符以及改变运算次序的圆括号连接而成的式子。操作数可以是常量、变量和函数，同时还可以是表达式。运算符包括单目运算符和双目运算符两类，单目运算符只要求一个操作数，并被放在该操作数的前面，双目运算符要求有两个操作数，并被放在这两个操作数的中间。单目运算符为取正’+’和取负’-’，双目运算符有加’+’,减’-’,乘’*’和除’/’等。为了简便起见，在我们的讨论中只考虑双目运算符。
如对于一个算术表达式2+5*6，乘法运算符’*’的两个操作数是它两边的5和6；对于加法运算符’+’的两个操作数，一个是它前面的2，另一个是它后面的5*6的结果即30。我们把双目运算符出现在两个操作数中间的这种习惯表示叫做算术表达式的中缀表示，这种算术表达式被称为中缀算术表达式或中缀表达式。
中缀表达式的计算比较复杂，它必须遵守以下三条规则：
(1) 先计算括号内，后计算括号外；
(2) 在无括号或同层括号内，先进行乘除运算，后进行加减运算，即乘除运算的优先级高于加减运算的优先级；
(3) 同一优先级运算，从左向右依次进行。
从这三条规则可以看出，在中缀表达式的计算过程中，既要考虑括号的作用，又要考虑运算符的优先级，还要考虑运算符出现的先后次序。因此，各运算符实际的运算次序往往同它们在表达式中出现的先后次序是不一致的，是不可预测的。当然凭直观判别一个中缀表达式中哪个运算符最先算，哪个次之，……，哪个最后算并不困难，但通过计算机处理就比较困难了，因为计算机只能一个字符一个字符地扫描，要想得到哪一个运算符先算，就必须对整个中缀表达式扫描一遍，一个中缀表达式中有多少个运算符，原则上就得扫描多少遍才能计算完毕，这样就太浪费时间了，显然是不可取的。
那么，能否把中缀算术表达式转换成另一种形式的算术表达式，使计算简单化呢? 回答是肯定的。波兰科学家卢卡谢维奇(Lukasiewicz)很早就提出了算术表达式的另一种表示，即后缀表示，又称逆波兰式，其定义是把运算符放在两个运算对象的后面。采用后缀表示的算术表达式被称为后缀算术表达式或后缀表达式。在后缀表达式中，不存在括号，也不存在优先级的差别，计算过程完全按照运算符出现的先后次序进行，整个计算过程仅需一遍扫描便可完成，显然比中缀表达式的计算要简单得多。例如，对于后缀表达式12!4!-!5!/，其中’!’字符表示成分之间的空格，因减法运算符在前，除法运算符在后，所以应先做减法，后做除法；减法的两个操作数是它前面的12和4，其中第一个数12是被减数，第二个数4是减数；除法的两个操作数是它前面的12减4的差(即8)和5，其中8是被除数，5是除数。
中缀算术表达式转换成对应的后缀算术表达式的规则是：把每个运算符都移到它的两个运算对象的后面，然后删除掉所有的括号即可。
例如，对于下列各中缀表达式：
(1) 3/5+6
(2) 16-9*(4+3)
(3) 2*(x+y)/(1-x)
(4) (25+x)*(a*(a+b)+b)
对应的后缀表达式分别为：
(1) 3!5!/!6!+
(2) 16!9!4!3!+!*!-
(3) 2!x!y!+!*!1!x!-!/
(4) 25!x!+!a!a!b!+!*!b!+!*
[color] 2. 后缀表达式求值的算法[/color]
后缀表达式的求值比较简单，扫描一遍即可完成。它需要使用一个栈，假定用S表示，其元素类型应为操作数的类型，假定为浮点型float，用此栈存储后缀表达式中的操作数、计算过程中的中间结果以及最后结果。假定一个后缀算术表达式以字符’@’作为结束符，并且以一个字符串的方式提供。喉缀表达式求值算法的基本思路是：把包含后缀算术表达式的字符串定义为一个输入字符串流对象，每次从中读入一个字符（空格作为数据之间的分隔符，不会被作为字符读入）时，若它是运算符，则表明它的两个操作数已经在栈S中，其中栈顶元素为运算符的后一个操作数，栈顶元素的下一个元素为运算符的前一个操作数，把它们弹出后进行相应运算即可，然后把运算结果再压入栈S中；否则，读入的字符必为操作数的最高位数字，应把它重新送回输入流中，然后把下一个数据作为浮点数输入，并把它压入到栈S中。依次扫描每一个字符（对于浮点数只需扫描它的最高位并一次输入整个浮点数）并进行上述处理，直到遇到结束符’@’为止，表明后缀表达式计算完毕，最终结果保存在栈中，并且栈中仅存这一个值，把它弹出返回即可。具体算法描述为：
float Compute (char* str)
//计算由str字符串所表示的后缀表达式的值，
---- //表达式要以'@'字符结束。
{
-- Stack S; //用S栈存储操作数和中间计算结果
-- InitStack(S); //初始化栈
-- istrstream ins(str); //把str定义为输入字符串流对象ins
-- char ch; //用于输入字符
-- float x; //用于输入浮点数
-- ins>>ch; //从ins流对象(即str字符串)中顺序读入一个字符
-- while(ch!='@')
-- { //扫描每一个字符并进行相应处理
---- switch(ch)
---- {
---- case '+':
------ x=Pop(S)+Pop(S);
------ break;
---- case '-':
------ x=Pop(S); // Pop(S)弹出减数
------ x=Pop(S)-x; //Pop(S)弹出的是被减数
------ break;
---- case '*':
------ x=Pop(S)*Pop(S);
------ break;
---- case '/':
------ x=Pop(S); // Pop(S)弹出除数
------ if(x!=0.0)
-------- x=Pop(S)/x; //Pop(S)弹出的是被除数
------ else { //除数为0时终止运行
-------- cerr<<"Divide by 0!"<<endl;
-------- exit(1);
------ }
------ break;
---- default: //读入的必为一个浮点数的最高位数字
------ ins.putback(ch); //把它重新回送到输入流中
------ ins>>x; //从字符串输入流中读入一个浮点数
---- }
---- Push(S,x); //把读入的一个浮点数或进行相应运算
---- //的结果压入到S栈中
---- ins>>ch; //输入下一个字符，以便进行下一轮循环处理
-- }
-- if(!StackEmpty(S))
-- { //若栈中仅有一个元素，则它是后缀表达式的值，否则为出错
---- x=Pop(S);
---- if(StackEmpty(S))
------ return x;
---- else {
------ cerr<<"expression error!"<<endl;
------ exit(1);
---- }
-- }
-- else { //若最后栈为空，则终止运行
---- cerr<<"Stack is empty!"<<endl;
---- exit(1);
-- }
}
此算法的运行时间主要花在while循环上，它从头到尾扫描后缀表达式中的每一个数据（每个操作数或运算符均为一个数据），若后缀表达式由n个数据组成，则此算法的时间复杂度为O(n)。此算法在运行时所占用的临时空间主要取决于栈S的大小，显然，它的最大深度不会超过表达式中操作数的个数，因为操作数的个数与运算符（假定把’@’也看作为一个特殊运算符，即结束运算符）的个数相等，所以此算法的空间复杂度也同样为O(n)。
假定一个字符串a为：
-- char a[30]="12 3 20 4 / * 8 - 6 * +@";
--对应的中缀算术表达式为12+(3*(20/4)-8)*6@，则使用如下语句调用上述函数得到的输出结果为54。
cout<<Compute(a)<<endl;
在进行这个后缀算术表达式求值的过程中，从第四个操作数入栈开始，每处理一个操作数或运算符后，栈S中保存的操作数和中间结果的情况如图所示。
图栈S中数据的变化
[color]3. 把中缀表达式转换为后缀表达式的算法[/color]
设以’@’字符作为结束符的中缀算术表达式已经保存在s1字符串中，转换后得到的后缀算术表达式拟存于s2字符串中。由中缀表达式转换为后缀表达式的规则可知：转换前后，表达式中的数值项的次序不变，而运算符的次序发生了变化，由处在两个运算对象的中间变为处在两个运算对象的后面，同时去掉了所有的括号。为了使转换正确，必须设定一个运算符栈，并在栈底放入一个特殊算符，假定为’@’字符，让它具有最低的运算符优先级，假定为数值0，此栈用来保存扫描中缀表达式得到的暂不能放入后缀表达式中的运算符，待它的两个运算对象都放入到后缀表达式以后，再令其出栈并写入到后缀表达式中。
把中缀表达式转换为后缀表达式算法的基本思路是从头到尾地扫描中缀表达式中的每个字符，对于不同类型的字符按不情况进行处理。若遇到的是空格则认为是分隔符，不需要进行处理；若遇到的是数字或小数点，则直接写入到s2中，并在每个数值的最后写入一个空格；若遇到的是左括号，则应把它压入到运算符栈中，待以它开始的括号内的表达式转换完毕后再出栈；若遇到的是右括号，则表明括号内的中缀表达式已经扫描完毕，把从栈底直到保存着的对应左括号之间的运算符依次退栈并写入s2串中；若遇到的是运算符，当该运算符的优先级大于栈顶运算符的优先级（加减运算符的优先级设定为1，乘除运算符的优先级设定为2，在栈中保存的特殊运算符’@’和’(’的优先级设定为0)时，表明该运算符的后一个运算对象还没有被扫描并放入到s2串中，应把它暂存于运算符栈中，待它的后一个运算对象从s1串中读出并写入到s2串中后，再另其出栈并写入s2串中；若遇到的运算符的优先级小于等于栈顶运算符的优先级，这表明栈顶运算符的两个运算对象已经被保存到s2串中，应将栈顶运算符退栈并写入到s2串中，对于新的栈顶运算符仍继续进行比较和处理，直到被处理的运算符的优先级大于栈顶运算符的优先级为止，然后另该运算符进栈即可。
按照以上过程扫描到中缀表达式结束符’@’时，把栈中剩余的运算符依次退栈并写入到后缀表达式中，再向s2写入表达式结束符’@’和字符串结束符’"0’，整个转换过程就处理完毕，在s2中就得到了转换成的后缀表达式。
例如，设中缀算术表达式s1为：10+(18+9*3)/15-6@，使用的运算符栈用R表示，则转换过程如下：
（1）开始时存放后缀表达式的字符串s2为空，R中压入有’@’算符，它具有最低的优先级0：
（表格略）
（2）当扫描到s1中的左括号时，s2和R中的数据变化如下：
（表格略）
（3）当扫描到s1中的数值3时，s2和R中的数据变化为：
（表格略）
（4）当扫描到s1中的右括号时，s2和R变为：
（表格略）
（5）当扫描到s1中的数值15时，s2和R又变为：
1--0-- --1--8-- --9-- --3-- --*--+--1--5-- -- -- -- -- -- --
@--+--/-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --
（6）当扫描到s1中的’@’字符时，s2和R为：
（表格略）
（7）当整个处理过程结束后，R栈为空，s2为：
将中缀算术表达式转换为后缀算术表达式的算法描述如下：
void Change(char* s1, char* s2)
//将字符串s1中的中缀表达式转换为存于字符串s2中的后缀表达式
{
-- Stack R; //定义用于暂存运算符的栈
InitStack(R); //初始化栈
-- Push(R,'@'); //给栈底放入'@'字符，它具有最低优先级0
-- int i,j;
-- i=0; //用于指示扫描s1串中字符的位置，初值为0
-- j=0; //用于指示s2串中待存字符的位置，初值为0
-- char ch=s1[i]; //ch保存s1串中扫描到的字符，初值为第一个字符
-- while(ch!='@')
-- { //顺序处理中缀表达式中的每个字符
---- if(ch==' ')
------ //对于空格字符不做任何处理，顺序读取下一个字符
------ ch=s1[++i];
---- else if(ch=='(')
---- { //对于左括号，直接进栈
------ Push(R,ch);
------ ch=s1[++i];
---- }
---- else if(ch==')')
---- { //对于右括号，使括号内的仍停留在栈中的运算符依次
------ //出栈并写入到s2中
------ while(Peek(R)!='(')
s2[j++]=Pop(R);
------ Pop(R); //删除栈顶的左括号
------ ch=s1[++i];
---- }
---- else if(ch=='+'||ch=='-'||ch=='*'||ch=='/')
---- { //对于四则运算符，使暂存在栈中的不低于ch优先级
------ //的运算符依次出栈并写入到s2中
------ char w=Peek(R);
------ while(Precedence(w)>=Precedence(ch))
{ // Precedence(w)函数返回运算符形参的优先级
-------- s2[j++]=w;
-------- Pop(R); w=Peek(R);
------ }
------ Push(R,ch); //把ch运算符写入栈中
------ ch=s1[++i];
---- }
else
{ //此处必然为数字或小数点字符
------ while(isdigit(ch)||ch=='.')
------ { //把一个数值中的每一位依次写入到s2串中
-------- s2[j++]=ch;
-------- ch=s1[++i];
------ }
------ s2[j++]=' '; //被转换后的每个数值后放入一个空格
---- }
-- }
//把暂存在栈中的运算符依次出栈并写入到s2串中
-- ch=Pop(R);
-- while(ch!='@') {
---- if(ch=='(') {
------ cerr<<"expression error!"<<endl;
------ exit(1);
---- }
---- else {
---- s2[j++]=ch;
---- ch=Pop(R);
---- }
-- }
//在后缀表达式的末尾放入表达式结束符和字符串结束符
-- s2[j++]='@';
-- s2[j++]='"0';
}
求运算符优先级的Precedence函数为：
int Precedence(char op)
//返回运算符op所对应的优先级数值
{
-- switch(op)
-- {
---- case '+':
case '-':
------ return 1; //定义加减运算的优先级为1
case '*':
---- case '/':
------ return 2; //定义乘除运算的优先级为2
-- -- case '(':
---- case '@':
---- default:
------ return 0; //定义在栈中的左括号和栈底字符的优先级为0
-- }
}
在转换算法中，中缀算术表达式中的每个字符均需要扫描一遍，对于扫描到的每个运算符，最多需要进行入栈、出栈和写入后缀表达式这三次操作，对于扫描到的数字或小数点，只需要把它直接写入到后缀表达式即可。所以，此算法的时间复杂度为O(n)，n为后缀表达式中字符的个数。该算法需要使用一个运算符栈，需要的深度不会超过中缀表达式中运算符的个数，所以此算法的空间复杂度至多也为O(n)。
利用表达式的后缀表示和堆栈技术只需要两遍扫描就可完成中缀算术表达式的计算，显然比直接进行中缀算术表达式计算的扫描次数要少得多。
在上述讨论的中缀算术表达式求值的两个算法中，把中缀表示转换为后缀表示的算法需要使用一个字符栈，而进行后缀表达式求值的算法又需要使用一个浮点数栈，这两个栈的元素类型不同，所以栈的类型无法作为全局量来定义，栈运算的函数也无法适应这种要求。为了解决这个问题，必须把Stack栈类型定义为模板类，把栈运算的函数定义为该类的公用成员函数，通过调用成员函数来实现栈的运算。这里对此不作深入讨论，留给读者作为练习。
假定采用类模板来定义Stack类和编写计算中缀算术表达式值的程序，若执行下面的主程序：
void main()
{
-- char a[30];
-- char b[30];
-- cout<<"请输入一个以'@'字符结束的中缀算术表达式："<<endl;
-- cin.getline(a,sizeof(a)); //从键盘上输入一行表示中缀算术表达
//式的字符串存入到字符数组a中
-- Change(a,b);
-- cout<<"对应的后缀算术表达式为："<<endl;
-- cout<<b<<endl;
-- cout<<"求值结果为："<<Compute(b)<<endl;
}
则得到的显示结果如下：
请输入一个以'@'字符结束的中缀算术表达式：
12+(3*(20/4)-8)*6@
对应的后缀算术表达式为：
12 3 20 4 /*8 -6 *+@
求值结果为：54
备注：网上有些资料中将波兰表示法的定义与逆波兰表示法定义写成一样，这是不对的。
波兰表示法是前缀表示法，即操作符在前，操作数在后；
而逆波兰表示法是后缀表示法，即操作数在前，操作符在后；
而普通表示法属中缀表示法，操作符在操作数的中间，优先级需要用括号来注明。