赋值语句的翻译（逆波兰式结果）

后缀表达式求值的算法: 后缀表达式的求值比较简单，扫描一遍即可完成。它需要使用一个栈，假定用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。