【练习】【栈】牛客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(); } };