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

た入场券 2022-05-09 07:56 152阅读 0赞

Problem Description

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

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

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

59*684/-3*\+\#  
Sample Output

57  
Hint

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

#include <iostream>
    
    using namespace std;
    
    int main()
    {
        int  A[10000];
        int p=0;
        char c;
        while(cin>>c!=NULL)
        {
           if(c=='*')
           {
               int t=A[p];
               p--;
               A[p]=A[p]*t;
           }
           else if(c=='/')
           {
               int t=A[p];
               p--;
               A[p]=A[p]/t;
           }
           else if(c=='+')
           {
               int t=A[p];
               p--;
               A[p]=A[p]+t;
           }
           else if(c=='-')
           {
               int t=A[p];
               p--;
               A[p]=A[p]-t;
           }
           else if(c=='#')
           {
               cout<<A[p];
               break;
           }
           else
           {
               p++;
               A[p]=(int)(c-'0');
           }
        }
        return 0;
    }

解析：后缀式求值：用数组模拟思路：  
如果是数字，则存入栈中，如果不是则对应相应的操作。而特别要注意的就是 char 类型的输入，最后要转化成int类型。

#include <stdio.h>
    #include <stdlib.h>
    
    int main()
    {
        char c;
        int A[10000];
        int top=0;
        while(scanf("%c",&c)!=EOF)
        {
            if(c=='*')
            {
                int a=A[top];
                top--;
                A[top]=A[top]*a;
            }
            else if(c=='/')
            {
                int a=A[top];
                top--;
                A[top]=A[top]/a;
            }
            else if(c=='+')
            {
                int a=A[top];
                top--;
                A[top]=a+A[top];
            }
            else if(c=='-')
            {
                int a=A[top];
                top--;
                A[top]=A[top]-a;
            }
            else if(c=='#')
            {
                printf("%d",A[top]);
                break;
            }
            else
            {
                top++;
                A[top]=(int)(c-'0');
            }
        }
        return 0;
    }

#include <iostream>
    #include <stack>
    #include <stdlib.h>
    #include <stdio.h>
    using namespace std;
    
    int main()
    {
        stack<int>mystack;
        char c;
        while(scanf("%c",&c)!=EOF)
        {
            if(c=='*')
            {
                int a=mystack.top();
                mystack.pop();
                mystack.top()=mystack.top()*a;
            }
            else if(c=='/')
            {
              int a=mystack.top();
                mystack.pop();
                mystack.top()=mystack.top()/a;
            }
            else if(c=='+')
            {
                int a=mystack.top();
                mystack.pop();
                mystack.top()=mystack.top()+a;
            }
            else if(c=='-')
            {
                int a=mystack.top();
                mystack.pop();
                mystack.top()=mystack.top()-a;
            }
            else if(c=='#')
            {
                printf("%d\n",mystack.top());
                break;
            }
            else
            {
                mystack.push(c-'0');
            }
        }
        return 0;
    }