P1449 后缀表达式

题目描述

所谓后缀表达式是指这样的一个表达式：式中不再引用括号，运算符号放在两个运算对象之后，所有计算按运算符号出现的顺序，严格地由左而右新进行（不用考虑运算符的优先级）。

本题中运算符仅包含 。保证对于 运算除数不为 0。特别地，其中 运算的结果需要向 0 取整（即与 C++ / 运算的规则一致）。

如： 对应的后缀表达式为：。在该式中，@ 为表达式的结束符号。. 为操作数的结束符号。

输入格式

输入一行一个字符串 ，表示后缀表达式。

输出格式

输出一个整数，表示表达式的值。

输入输出样例 #1

输入 #1

3.5.2.-*7.+@

输出 #1

16

输入输出样例 #2

输入 #2

10.28.30./*7.-@

输出 #2

-7

说明/提示

数据保证，，答案和计算过程中的每一个值的绝对值不超过 。

观察例子：3.5.2.-7.+@，其正确运算顺序为3（5-2）+7

我们发现，当遇到运算符时，后来的5和2是最先要进行-运算的，得到的结果再和最先的数字3进行*运算，这明显符合栈的“后进先出”性质。

于是，思路就很明了了，我们需要一个栈依次存储遍历到的数字，遇到运算符再依次出栈，进行运算。

具体代码如下：

#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<deque>
#include<cmath>
#include<string>
using namespace std;

long long str_to_num(string strnum);

int main(){
    string s;
    cin>>s;

    stack<long long> st;
    string strnum;
    int j=0,n=s.size();
    long long a=0,b=0,c=0;
    for(int i=0;i<n;i++){
        if(s.at(i)=='@') break;
        if(s.at(i)>='0' && s.at(i)<='9'){
            j=s.find('.',i);
            strnum=s.substr(i,j-i);
            i=j;
            st.push(str_to_num(strnum));
        }else{
            b=st.top();
            st.pop();
            a=st.top();
            st.pop();
            if(s.at(i)=='-') c=a-b;
            else if(s.at(i)=='+') c=a+b;
            else if(s.at(i)=='*') c=a*b;
            else  c=a/b;
            st.push(c);
        }
    }
    long long out=st.top();
    st.pop();
    cout<<out;
    return 0;
}
long long str_to_num(string strnum){
    long long num=0;
    int le=strnum.size(); 
    for(int i=0;i<le;i++){
        num*=10;
        num+=(strnum.at(i)-'0');
    }
    return num;
}