算法练习-逆波兰表达式求值（思路+流程图+代码）

本文介绍: 根据逆波兰表示法，求表达式的值。有效的运算符包括+，·，*，/。每个运算对像可以是整数，也可以是另一个逆波兰表达式。说明：整数除法只保留整数部分。给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为0的情况。示例1:输入：[“2″，”1″，”+”，”3″，”*门输出：9解释：该算式转化为常见的中缀算术表达式为：(2+1)*3)=9

难度：中等

分类：栈与队列

难度与分类由我所参与的培训课程提供，但需要注意的是，难度与分类仅供参考。且所在课程未提供测试平台，故实现代码主要为自行测试的那种，以下内容均为个人笔记，旨在督促自己认真学习。

根据逆波兰表示法，求表达式的值。
有效的运算符包括+，·，*，/。每个运算对像可以是整数，也可以是另一个逆波兰表达式。

说明：

整数除法只保留整数部分。给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数
为0的情况。

#include <iostream> // 包含输入输出流库，用于标准输入输出
#include <stack> // 包含栈库，用于存储操作数
#include <vector> // 包含向量库，用于存储输入的逆波兰表达式
#include <string> // 包含字符串库，用于操作字符串
#include <cstdlib> // 包含标准库，用于字符串转整数的函数

using namespace std; // 使用标准命名空间

int evalRPN(vector<string>& tokens) { // 定义了一个函数，用于计算逆波兰表达式的值，参数为存储表达式的向量
    stack<int> st; // 创建一个整型栈对象，用于存储操作数
    for (string& token : tokens) { // 遍历逆波兰表达式的每个元素
        if (token == "+") { // 如果当前元素为加号
            int num2 = st.top(); // 取出栈顶元素作为第二个操作数
            st.pop(); // 弹出栈顶元素
            int num1 = st.top(); // 取出新的栈顶元素作为第一个操作数
            st.pop(); // 弹出栈顶元素
            st.push(num1 + num2); // 将计算结果入栈
        } else if (token == "-") { // 如果当前元素为减号，逻辑同上
            int num2 = st.top();
            st.pop();
            int num1 = st.top();
            st.pop();
            st.push(num1 - num2);
        } else if (token == "*") { // 如果当前元素为乘号，逻辑同上
            int num2 = st.top();
            st.pop();
            int num1 = st.top();
            st.pop();
            st.push(num1 * num2);
        } else if (token == "/") { // 如果当前元素为除号，逻辑同上
            int num2 = st.top();
            st.pop();
            int num1 = st.top();
            st.pop();
            st.push(num1 / num2);
        } else { // 如果当前元素为数字
            st.push(stoi(token)); // 将字符串转换为整数后入栈
        }
    }
    return st.top(); // 返回栈中最终的结果
}

int main() { // 主函数
    vector<string> tokens = {"2", "1", "+", "3", "*"}; // 创建一个存储逆波兰表达式的向量，其中元素为字符串
    int result = evalRPN(tokens); // 调用 evalRPN 函数计算表达式的值
    cout << result << endl; // 输出计算结果

    tokens = {"4", "13", "5", "/", "+"}; // 更新逆波兰表达式
    result = evalRPN(tokens); // 调用 evalRPN 函数计算表达式的值
    cout << result << endl; // 输出计算结果

    return 0; // 返回 0，表示正常结束程序
}