时间限制： 1.0 秒

空间限制： 512 MB

题目背景

逆波兰表示法是一种将运算符（operator）写在操作数（operand）后面的描述程序（算式）的方法。

举个例子，我们平常用中缀表示法描述的算式 (1+2)*(5+4)，改为逆波兰表示法之后则是 1 2 + 5 4 + *。

相较于中缀表示法，逆波兰表示法的优势在于不需要括号。

给定以下二叉树的节点接口定义：

struct BinNode
{
    std::string x; // 操作符或操作数
    BinNode *lc, *rc; // 左儿子和右儿子
    BinNode(std::string s = "", BinNode *l = nullptr, BinNode *r = nullptr)
            :x(s), lc(l), rc(r) {}
};

其中关于 C++ 的默认构造函数请在互联网自行查询相关资料。

题目描述

请设计一个算法，将逆波兰表达式构造成对应的表达式树。并返回对应的树根节点。

交互方式

这是一道函数式交互题，不需要选手考虑输入输出，也不要从标准输入读入数据，或将任何内容输出到标准输出，否则会影响判题。

你提交的代码需要包含头文件 bintree.h。

你需要实现函数 BinNode *build_expr(const std::vector<std::string>& rpn)，传入参数为一个字符串数组，代表逆波兰表达式（动态数组的秩从 0 开始）。

以下我们给出一个代码提交实例（只将第一个操作数构造成一个节点，子节点在未传入参数的情况下根据【题目背景】默认为空，仅作为实例，不保证能得分）：

#include "bintree.h"
BinNode *build_expr(const std::vector<std::string>& rpn)
{
    BinNode *rt = new BinNode(rpn[0]);
    return rt;
}

白盒交互库实例

具体请见附加文件区的 interactor.cc 和 bintree.h。本题直接采用白盒交互库进行评测。

如果你本地的实现代码为 main.cc，则将交互库放在同一目录下，在 Linux 系统中输入以下命令行即可运行：

g++ main.cc interactor.cc -Wall -std=c++20 -o foo -lm -O2 -I/include

在 Windows 下会生成 foo.exe，在 Linux 下会生成 foo，你可以输入 .\foo.exe 或者 ./foo 命令行执行该文件。或者将交互库接口与你实现的函数统一在单代码文件中进行本地调试即可。

白盒交互库会先输入完整的 RPN 表达式，每个操作数/运算符之间用空格分隔（保证操作数只由不超过 5 个大写字母组成，运算符只会是 +、-、*、/ 中的一个）。

接下来白盒交互库会无脑嵌套括号进行表达式树中序遍历的输出，即中缀表达式。

A B C D - * + E F + +

(A+(B*(C-D)))+(E+F)

样例 1 解释

该逆波兰表达式对应的表达式树如图。

子任务

对于所有数据，保证逆波兰表达式的元素个数不超过 $2\times 10^5$，且一定为合法。

本题无数据梯度，需要通过全部数据获得所有分数。

来源

清华 826 考研初试 2016 - 算法大题（1）