逆波兰表达式

GitHub跳转原题关系图返回列表

递归下降求值前缀表达式：当前 token 为运算符时递归求左右子式，否则返回浮点值。

OJ: roj

题目 ID: 1198

难度:入门

标签:递归表达式求值前缀表达式

创建: 2026-09-29 23:05

更新: 2026-10-05 05:19

目录

  1. 题目描述
  2. 思路
  3. 参考代码

题目描述

逆波兰表达式把运算符放在两个运算数之前，如 + 2 3 表示 2 + 3、* + 2 3 4 表示 (2 + 3) * 4。输入一行，运算符与浮点数之间用空格分隔；输出表达式的值，保留 6 位小数。

思路

前缀表达式的第一个 token 是当前子树的根：若为运算符，则后面紧跟的连续两段分别是左、右子表达式，递归求值后合并；若为数字，直接返回。按顺序读入所有 token，一次递归即可得到结果。

参考代码

Python 版：

python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-29 23:05
# update_at: 2026-09-29 23:05

import sys
from collections.abc import Iterator


def eval_expr(tokens: Iterator[str]) -> float:
    """递归求值前缀表达式：当前 token 是运算符则取左右子式，否则为数字。"""
    tok = next(tokens)
    if tok in "+-*/":
        left = eval_expr(tokens)
        right = eval_expr(tokens)
        if tok == "+":
            return left + right
        if tok == "-":
            return left - right
        if tok == "*":
            return left * right
        return left / right
    return float(tok)


def solve() -> None:
    data = sys.stdin.buffer.read().decode().split()
    tokens = iter(data)
    ans = eval_expr(tokens)
    print(f"{ans:.6f}")


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 05:19
 * update_at: 2026-10-05 05:19
 */
#include <iostream>
#include <iomanip>
#include <cstdlib>
using namespace std;

typedef long long ll;

const int MAXN = 100005; // 最多 token 数量

char tok[MAXN][32]; // 每个 token
int n;              // token 总数
int pos;            // 当前读取位置

// 递归求值前缀表达式
long double eval_expr() {
    char *s = tok[pos++];
    if (s[0] == '+' || s[0] == '-' || s[0] == '*' || s[0] == '/') {
        // 当前是运算符，递归求左右两个子表达式的值
        long double left = eval_expr();
        long double right = eval_expr();
        if (s[0] == '+') return left + right;
        if (s[0] == '-') return left - right;
        if (s[0] == '*') return left * right;
        return left / right;
    }
    // 当前是数字，直接返回浮点值
    return strtold(s, NULL);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // 读入所有 token
    while (cin >> tok[n]) {
        ++n;
    }

    pos = 0;
    long double ans = eval_expr();

    cout.setf(ios::fixed);
    cout << setprecision(6) << (double)ans << "\n";
    return 0;
}