Skip to main content

逆波兰表达式求值

· 5 min read
Eureka X
Eureka X
Mr.Nobody

力扣面试经典——150题​

💡 参考代码：​

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/**
 * 逆波兰表达式求值函数
 * @param tokens 字符串数组，表示逆波兰表达式
 * @param tokensSize 数组长度
 * @return 表达式的计算结果
 */
int evalRPN(char ** tokens, int tokensSize){
    // 使用数组模拟栈，存储操作数
    int stack[tokensSize];
    // 栈顶指针，指向下一个空位
    int top = 0;
    
    // 遍历所有token
    for (int i = 0; i < tokensSize; i++) {
        char* token = tokens[i];
        
        // 判断当前token是否为操作符
        if (strlen(token) == 1 && strchr("+-*/", token[0])) {
            // 取出栈顶两个元素作为操作数
            // 注意：第二个操作数先出栈
            int num2 = stack[--top];
            int num1 = stack[--top];
            
            // 根据操作符进行相应运算
            switch (token[0]) {
                case '+':
                    stack[top++] = num1 + num2;
                    break;
                case '-':
                    stack[top++] = num1 - num2;
                    break;
                case '*':
                    stack[top++] = num1 * num2;
                    break;
                case '/':
                    stack[top++] = num1 / num2;
                    break;
            }
        } else {
            // 当前token是数字，转换为整数并入栈
            stack[top++] = atoi(token);
        }
    }
    
    // 最终栈中只剩一个元素，即为表达式结果
    return stack[0];
}

📖 总结：​

点击展开题目总结

🤔 逆波兰表达式求值

1️⃣ 题目核心信息​

🎯 功能描述：计算逆波兰表达式（后缀表达式）的值

📥 输入输出：

  • 输入：tokens - 字符串数组，表示逆波兰表达式；tokensSize - 数组长度
  • 输出：返回表达式的计算结果（整数）

2️⃣ 实现原理​

💡 核心思路：使用栈数据结构处理逆波兰表达式，遇到数字入栈，遇到操作符出栈计算再入栈

📋 实现步骤：

  1. 创建栈数组用于存储操作数
  2. 遍历 tokens 数组中的每个元素
  3. 若为数字则转换为整数并入栈
  4. 若为操作符则出栈两个操作数进行运算，结果入栈
  5. 返回栈中最终剩余的元素

3️⃣ 关键点解析​

🎯 代码技巧​

  • 使用数组模拟栈结构，提高效率
  • 巧妙利用 strchr 判断操作符字符
  • 注意操作数出栈顺序：先出栈的是第二个操作数
  • 利用 C 语言整数除法天然向零截断特性

4️⃣ 使用场景​

✅ 适用情况：​

  • 计算后缀表达式
  • 表达式求值解析器
  • 栈结构应用演示

⚠️ 前提条件：​

  • 输入保证是有效的逆波兰表达式
  • 不会出现除零运算
  • 所有中间结果和最终结果在 32 位整数范围内

5️⃣ 复杂度分析​

  • ⏱️ 时间复杂度：O(n)，其中 n 是 tokens 数组的长度，需要遍历一次数组
  • 💾 空间复杂度：O(n)，栈的最大深度不会超过 tokens 数组的长度

6️⃣ 注意事项​

🚩 边界情况：​

  • 输入数组只有一个数字元素
  • 负数的处理
  • 除法向零截断的情况

💥 易错点：​

  • 操作数出栈顺序容易搞错
  • 操作符判断逻辑不严谨
  • 忘记处理负数字符串转换

7️⃣ 补充说明​

假设我们有逆波兰表达式：["2", "1", "+", "3", "*"]，它表示中缀表达式 (2 + 1) * 3。

  1. 初始化阶段
  • 创建一个大小为5的 stack 数组（因为 tokensSize = 5）
  • 设置栈顶指针 top = 0
  1. 处理每个token

  • 处理 "2"

    • 检查发现不是操作符，将其转换为整数2并入栈
    • stack[0] = 2
    • top = 1

  • 处理 "1"

    • 检查发现不是操作符，将其转换为整数1并入栈
    • stack[1] = 1
    • top = 2

  • 处理 "+"

    • 检查发现是操作符

    • 从栈中取出两个操作数：

    • num2 = stack[--top] = stack[1] = 1 （top变为1）

    • num1 = stack[--top] = stack[0] = 2 （top变为0）

    • 执行加法运算：2 + 1 = 3

    • 将结果3入栈：

    • stack[top++] = 3 （stack[0] = 3，top变为1）

  • 处理 "3"

    • 检查发现不是操作符，将其转换为整数3并入栈
    • stack[1] = 3
    • top = 2

  • 处理 "*"

    • 检查发现是操作符
    • 从栈中取出两个操作数：
    • num2 = stack[--top] = stack[1] = 3 （top变为1）
    • num1 = stack[--top] = stack[0] = 3 （top变为0）
    • 执行乘法运算：3 * 3 = 9
    • 将结果9入栈：
    • stack[top++] = 9 （stack[0] = 9，top变为1）
  1. 返回结果
  • 遍历完成，栈中只剩一个元素 stack[0] = 9
  • 函数返回值为 9

核心思想​

该函数使用了栈数据结构来处理逆波兰表达式：

  • 遇到数字就入栈
  • 遇到操作符就弹出栈顶两个元素进行运算，再将结果入栈
  • 最终栈中剩下的唯一元素就是表达式的结果

这种处理方式避免了中缀表达式中复杂的运算符优先级判断，使得计算过程非常直观高效。

加载评论中...