Description

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

Input

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

Output

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

Sample

Input

59*684/-3*+#

Output

57

Hint

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

答案：

基本栈：

#include <iostream>
#include<bits/stdc++.h>
#define ll long long
using namespace std;

int main()
{
    char s[1111];
    cin>>s;
    int i;
    int st[1111];
    int top=0;
    for(i=0; s[i]!='#'; i++)
    {
        if(s[i]>='1'&&s[i]<='9')
            st[++top]=s[i]-'0';
        else if(s[i] == '+' || s[i] == '-' || s[i] == '*' || s[i] == '/')
        {
            int x,y;
            y=st[top--];
            x=st[top--];
            if(s[i]=='+')
            {
                st[++top]=x+y;
            }
            else if(s[i]=='-')
            {
                st[++top]=x-y;
            }
            else if(s[i]=='*')
            {
                st[++top]=x*y;
            }
            else if(s[i]=='/')
            {
                st[++top]=x/y;
            }
        }
    }
    cout<<st[top]<<endl;
    return 0;
}

STL栈：

#include <iostream>
#include<bits/stdc++.h>
#define ll long long
using namespace std;
stack<int>dp;

int main()
{
    char s[1111];
    cin>>s;
    int i;
    for(i=0; s[i]!='#'; i++)
    {
        if(s[i]>='1'&&s[i]<='9')
            dp.push(s[i]-'0');
        else if(s[i] == '+' || s[i] == '-' || s[i] == '*' || s[i] == '/')
        {
            int x,y;
            y=dp.top();
            dp.pop();
            x=dp.top();
            dp.pop();
            if(s[i]=='+')
            {
                dp.push(x+y);
            }
            else if(s[i]=='-')
            {
                dp.push(x-y);
            }
            else if(s[i]=='*')
            {
                dp.push(x*y);
            }
            else if(s[i]=='/')
            {
                dp.push(x/y);
            }
        }
    }
    cout<<dp.top()<<endl;
    return 0;
}