【NC212914】牛牛与后缀表达式

本文主要是介绍【NC212914】牛牛与后缀表达式，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

牛牛与后缀表达式

栈

思路

栈基本问题：表达式求值

设置一个栈，当读入的 $t o k e n$ 是操作数时，就将其转化为数字并入栈，如果是运算符，则将栈顶的两个操作数出栈后进行运算再入栈（如果是合法的表达式的话在调用运算符的时候栈中一定有大于等于两个的操作数存在），最后，栈中只会存在一个数字，这个数字就是表达式的计算结果。

代码

class Solution {public:/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** 给定一个后缀表达式，返回它的结果* @param str string字符串* @return long长整型*/long long legalExp(string str) {// write code herestack<long long> stk;string token;int n = str.size(), i = 0, j = 0;long long a = 0, b = 0;while (i < n) {if (isdigit(str[i])) {// 如果当前字符是数字，那么就读取整个操作数token.clear();while (i < n && isdigit(str[i])) {token.push_back(str[i]);i++;}// 操作数入栈stk.emplace(stoll(token));continue;} else if (str[i] == '#') {// 如果当前字符是操作数结束符，则不管i++;continue;}// 如果是运算符// 那么先得到操作数a = stk.top();stk.pop();b = stk.top();stk.pop();// 再进行运算if (str[i] == '+') {// 加法运算stk.emplace(a + b);} else if (str[i] == '-') {// 减法运算stk.emplace(b - a);} else if (str[i] == '*') {// 乘法运算stk.emplace(a * b);}i++;}// 如果是合法的后缀表达式，那么运算完毕之后// 栈中只有一个数，即为表达式结果return stk.top();}
};