数据结构实验之栈三：后缀式求值

 

Time Limit: 1000MS Memory limit: 65536K

题目描述

对于一个基于二元运算符的后缀表示式（基本操作数都是一位正整数），求其代表的算术表达式的值。

输入

输入一个算术表达式的后缀式字符串，以‘#’作为结束标志。

输出

求该后缀式所对应的算术表达式的值，并输出之。

示例输入

59*684/-3*+#

示例输出

57

提示

基本操作数都是一位正整数!

来源

 

示例程序

题解：

先解释下后缀式吧：

后缀表达式　　不包含，放在两个运算对象的后面，所有的计算按运算符出现的顺序，严格从左向右进行（不再考虑运算符的优先规则，如：(2 + 1) * 3 ， 即2 1 + 3 *

运用后缀表达式进行计算的具体做法：

先建一个空栈S，从左到右读后缀表达式，如果读到操作数（一般是数字）就将它压入栈S中，如果读到n元运算符（即需要参数个数为n的运算符）则取出，由栈顶向下的n项按操作符运算，再将运算的结果代替原来栈顶的n项，压入栈中，如果后缀式未读完，则重复上面的过程，最后输出栈顶的数值作为结束。

#include 
     
      #include 
      
       #include 
       
        using namespace std;int main(){    int num[101];//定义栈存储操作数    int i=0;//标记变量    char ch;//输入值    while((scanf("%c",&ch) && ch != '#'))//输入后缀表达式，当输入为‘#’时停止    {        if(ch >= '0' && ch <= '9')            num[i++]=ch-'0';//从左到右开始读后缀表达式，如果读到的是数字就压入栈中        else        {
    //如果是操作符则进行相应的运算            int n=num[i-2],m=num[i-1];//提取栈顶的两个元素            int k;//暂时存储计算值            if(ch == '+')                k=n+m;            else if(ch == '-')                k=n-m;            else if(ch == '*')                k=n*m;            else if(ch == '/')                k=n/m;            i=i-2;//删除进行运算了的数            num[i++]=k;//将运算后的数值压入栈顶        }    }    printf("%d\n",num[0]);//读取结束后栈中只剩后缀式的求值结果，输出    return 0;}