【练习】【栈】牛客NC212914牛牛与后缀表达式

题目

给定牛牛一个后缀表达式s，计算它的结果，例如，1+1对应的后缀表达式为1#1#+，‘#’作为操作数的结束符号。
其中，表达式中只含有‘+’、’-‘、’*‘三种运算，不包含除法。本题保证表达式一定合法，且计算过程和计算结果的绝对值一定不会超过10^18

示例1

输入

“1#1#+”

返回值

2

示例2

输入

“12#3#+15#*”

返回值

225

来源：牛客NC212914牛牛与后缀表达式

思路（注意事项）

此题模板与acwing表达式求值模板类似，但是比那道题简单很多，不用考虑符号优先级、不用额外处理括号、不用额外的栈来存放符号。前面这题做会，这道题就是小菜一碟。

纯代码

class Solution {
private:stack<long long> num;void eval(char c){long long a, b,ans;a = num.top();num.pop();b = num.top();num.pop();if (c == '+') ans = a + b;else if (c == '-') ans = b - a;else if (c == '*') ans = b * a;num.push(ans);}
public:long long legalExp(string str) {for (int i = 0; i < str.size(); i ++){if (isdigit(str[i])){long long x = 0, j = i;while (j < str.size() && str[j] != '#'){x = x * 10 + str[j] - '0';j ++;}num.push(x);i = j - 1;}else if (str[i] == '#') continue;else eval(str[i]);}return num.top();}
};

题解（加注释）

#include <stack>
#include <string>
#include <cctype>// 定义一个解决方案类，用于处理后缀表达式的计算
class Solution {
private:// 定义一个存储长整型的栈，用于存放操作数std::stack<long long> num;// 该函数用于执行具体的运算操作// 参数 c 为运算符void eval(char c){// 定义三个长整型变量，a 和 b 用于存储操作数，ans 用于存储运算结果long long a, b, ans;// 从栈中取出栈顶元素作为第一个操作数a = num.top();// 取出后将该元素从栈中移除num.pop();// 再从栈中取出栈顶元素作为第二个操作数b = num.top();// 取出后将该元素从栈中移除num.pop();// 根据运算符 c 进行不同的运算if (c == '+') {// 若为加法运算符，将两个操作数相加得到结果ans = a + b;} else if (c == '-') {// 若为减法运算符，用第二个操作数减去第一个操作数得到结果ans = b - a;} else if (c == '*') {// 若为乘法运算符，将两个操作数相乘得到结果ans = b * a;}// 将运算结果压入栈中num.push(ans);}
public:// 该函数用于计算后缀表达式的值// 参数 str 为后缀表达式字符串// 返回值为计算得到的结果，类型为长整型long long legalExp(std::string str) {// 遍历后缀表达式字符串中的每个字符for (int i = 0; i < str.size(); i++){// 判断当前字符是否为数字if (std::isdigit(str[i])){// 若为数字，初始化一个长整型变量 x 用于存储该数字的值long long x = 0;// 定义一个临时变量 j 用于从当前位置开始向后扫描数字int j = i;// 当未扫描到字符串末尾且当前字符不是分隔符 '#' 时while (j < str.size() && str[j] != '#'){// 将之前的数字乘以 10 并加上当前字符对应的数字值x = x * 10 + (str[j] - '0');// 指针向后移动一位j++;}// 将完整的数字压入操作数栈中num.push(x);// 由于 while 循环结束后 j 已经指向下一个非数字字符，所以将 i 更新为 j - 1// 以便 for 循环的 i++ 能正确处理下一个字符i = j - 1;} // 若当前字符为分隔符 '#'else if (str[i] == '#') {// 跳过该字符，继续处理下一个字符continue;} // 若当前字符为运算符else {// 调用 eval 函数进行相应的运算eval(str[i]);}}// 遍历结束后，栈顶元素即为后缀表达式的计算结果，将其返回return num.top();}
};