逆波兰表达式求值算法与实例解析

逆波兰表达式（Reverse Polish Notation, RPN）是一种非标准的数学表达式书写方式，它的操作符位于其操作数之后，而不是像我们常见的中缀表达式那样放在操作数之间。在IT领域，特别是算法设计中，逆波兰表达式求值是一个经典的计算问题，它通常用于处理递归下降解析器或者表达式计算器等场景。 在给定的问题中，我们被要求实现一个函数`evalRPN`，接收一个由字符串组成的向量`tokens`，这些字符串代表了逆波兰表达式中的元素。`tokens`中包含两种类型的操作：整数和算符（+、-、*、/）。任务是根据逆波兰规则，计算出这些表达式的值。 **核心算法步骤**： 1. **初始化**： - 创建一个栈（vector<int> stk），大小为`tokens.length()`的一半加一，这是为了适应可能的最坏情况，即表达式完全由数字组成，此时栈顶将存储一半的元素。 - 初始化索引`index`为-1，用于追踪当前操作数的位置。 2. **遍历tokens**： - 对于每个`tokens[i]`： - 如果它是一个整数（长度大于1或首字符是数字），则将其转换为整数并压入栈（index++）。 - 否则，它是一个算符： - 减少栈顶的索引，因为操作数在栈顶，操作符在下面。 - 根据算符执行相应的操作： - 如果是'+'，栈顶的两个数相加（stk[index] += stk[index+1]）。 - 如果是'-'，栈顶的两个数相减（stk[index] -= stk[index+1]）。 - 如果是'*'，栈顶的两个数相乘（stk[index] *= stk[index+1]）。 - 如果是'/'，整数除法，只保留整数部分，即`stk[index] = stk[index] * (int)(stk[index+1] / stk[index+1])`，这里需要注意的是，除法可能涉及到浮点数，但题目要求只保留整数部分。 3. **结果**： - 遍历结束后，栈中只剩下一个元素，即最终的结果。 **代码实现**（C++示例）： ```cpp class Solution { public: int evalRPN(vector<string>& tokens) { int n = tokens.size(); vector<int> stk((n + 1) / 2); int index = -1; for (int i = 0; i < n; i++) { string& token = tokens[i]; if (token.length() > 1 || isdigit(token[0])) { index++; stk[index] = atoi(token.c_str()); } else { switch (token[0]) { case '+': index--; stk[index] += stk[index + 1]; break; case '-': index--; stk[index] -= stk[index + 1]; break; case '*': index--; stk[index] *= stk[index + 1]; break; case '/': index--; stk[index] = stk[index] * (int)(stk[index + 1] / stk[index + 1]); break; } } } return stk[0]; } }; ``` 逆波兰表达式求值问题涉及栈的运用，通过维护一个操作数栈，逐个处理输入的元素，遵循后进先出的原则来完成表达式的计算。这种问题常作为面试题出现，旨在考察编程基础和算法思维能力。理解并熟练掌握这个算法，对于处理更复杂的计算和表达式解析场景至关重要。