牛客编程巅峰赛S2第5场-牛牛与后缀表达式(利用栈实现)

比赛链接请点击

牛牛与后缀表达式

• 题目描述

题目描述

给定牛牛一个后缀表达式s，计算它的结果，例如，1+1对应的后缀表达式为1#1#+，‘#’作为操作数的结束符号。

其中，表达式中只含有‘+’、’-‘、’*‘三种运算，不包含除法。
本题保证表达式一定合法，且计算过程和计算结果的绝对值一定不会超过10^{18}

示例1

输入：“1#1#+”
返回值：2
说明：1#1#+这个后缀表达式表示的式子是1+1，结果为2

示例2

输入："12#3#+15# * "
返回值：225
说明： 12#3#+15#*这个后缀表达式表示的式子是(12+3)*15，结果为225

备注

1≤表达式中操作数≤1e9
1≤表达式长度≤1e6

解题思路

用一个栈来存储数据，每次遇到数就压入栈内；
遇到符号，就弹出两个数进行计算，然后把结果再压入栈内。

代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 给定一个后缀表达式，返回它的结果
     * @param str string字符串 
     * @return long长整型
     */
    long long solve(string str) {
        // write code here
        stack<long long>s;
        long long re=0,temp=0;
        long long num1,num2;
        int i;
        for(i=0;i<str.size();i++){
            if(str[i]>='0'&&str[i]<='9'){
                temp*=10;//在这里用一个变量temp来存数，每次*10再加上本位的数
                temp+=str[i]-'0';
            }
            else if(str[i]=='#') {
                s.push(temp);
                temp=0;
            }
            else{
                num1=s.top();
                s.pop();
                num2=s.top();
                s.pop();
                if(str[i]=='+') s.push(num2+num1);
                if(str[i]=='-') s.push(num2-num1);
                if(str[i]=='*') s.push(num2*num1);
            }
        }
        return s.top();
    }
};

本文地址：https://blog.csdn.net/weixin_41983309/article/details/110454275