生成运算树

题目

题目描述

在某种脚本语言里，有一个形如 x+(a+pi-xn)+eps 的运算表达式，该表达式由以下元素构成：

• 操作数：所有操作数均为变量，变量名由全小写字母组成，且长度不超过 10 个字符。
• 操作符：仅存在 +、- 这两种双目运算符。
• 括号：用于改变运算的优先级。当运算优先级相同时，表达式从左至右进行计算。

给出一个运算表达式 calExpression，为便于计算，需将其转化为二叉树的表达形式。树中每个子树的计算结果会用于更上层子树的计算，以此清晰展示运算次序。最后按先序遍历方式输出树的节点序列。

示例

例如，某个运算表达式转换为相应的运算树（此处因无法直接展示图片，您可根据描述自行想象）。

输入

输入为运算表达式 calExpression，此表达式仅包含小写字母以及 +、-、(、) 字符，字符串长度不超过 1000。用例确保输入的字符串是一个合法的运算表达式。

输出

输出为一个字符串数组，数组里每个元素的值为节点中的操作数或者运算符。

算法标签: 二叉树, $dfs$, 模拟, *递归下降算法

思路

将整个表达式根据操作符分解, 如果遇到括号构建子树, 按照递归的形式进行建树, 然后直接进行$pre$遍历

具体的逻辑就是首先处理整个表达式, 按照左边表达式, 中间操作符, 右边表达式进行处理, 如果当前位置是运算符, 那么解析左右两个表达式, 然后构建树的节点
然后对于解析过程中如果出现了括号中的表达式, 需要调用$build$函数进行处理构建出括号中的表达式如果不是表达式说明就是变量, 返回变量节点即可

代码

#include <algorithm>
#include <cstring>
#include <string>
#include <vector>using namespace std;struct Node {string val;Node *ls;Node *rs;Node(string v) : val(v), ls(nullptr), rs(nullptr) {}Node(string v, Node *l, Node *r) : val(v), ls(l), rs(r) {}
};string s;
int i = 0;
vector<string> ans;Node *parse();Node *build();//获取当前字符
char get() {while (i < s.size() && s[i] == ' ') i++;if (i >= s.size()) return '\0';return s[i];
}//获取当前位置的字符, 并且向后样移动以一位
char move() {char c = get();if (c != '\0') i++;return c;
}// 获取变量名
string get_var() {string res;while (isalpha(get())) res += move();return res;
}//如果当前位置是括号中的表达式, 将括号中表达式构建为一棵树, 否则就是变量, 构建变量节点
Node *parse() {if (get() == '(') {move();Node *u = build();if (get() == ')') move();return u;} else {string val = get_var();return new Node(val);}
}//递归的构建树
Node *build() {Node *ls = parse();while (true) {char op = get();if (op == '+' || op == '-') {move();Node *rs = parse();//构造当前节点Node *u = new Node(string(1, op), ls, rs);ls = u;} else break;}return ls;
}//前序遍历累加答案
void pre_dfs(Node *u) {if (u == nullptr) return;ans.push_back(u->val);pre_dfs(u->ls);pre_dfs(u->rs);
}void delete_tree(Node *root) {if (root == nullptr) return;delete_tree(root->ls);delete_tree(root->rs);delete root;
}class Solution {
public:vector<string> GetExpressionTree(const string &calExpression) {s = calExpression;i = 0;ans.clear();Node *root = build();pre_dfs(root);delete_tree(root);return ans;}
};

*后续$AC$代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <string>using namespace std;string s;
int i = 0;
vector<string> ans;
struct Node {string val;Node *ls, *rs;Node (string v) : val(v), ls(nullptr), rs(nullptr) {};Node (string v, Node *l, Node *r) : val(v), ls(l), rs(r) {};
};Node *build();
Node *parse();char get() {while (i < s.size() && s[i] == ' ') i++;if (i > s.size()) return '\0';return s[i];
}char move() {char c = get();if (c != '\0') i++;return c;
}string get_var() {string res;while (isalpha(get())) res += move();return res;
}Node *build() {Node *ls = parse();while (true) {char op = get();if (op == '+' || op == '-') {move();Node *rs = parse();Node *u = new Node(string(1, op), ls, rs);ls = u;}else break;}return ls;
}Node *parse() {if (get() == '(') {move();Node *u = build();if (get() == ')') move();return u;}else {string val = get_var();return new Node(val);}
}void dfs(Node *u) {if (u == nullptr) return;ans.push_back(u->val);dfs(u->ls);dfs(u->rs);
}void del(Node *u) {if (u == nullptr) return;del(u->ls);del(u->rs);delete u;
}class Solution {
public:vector<string> GetExpressionTree(const string &calExpression) {s = calExpression;i = 0;ans.clear();Node *u = build();dfs(u);del(u);return ans;}
};