HOJ.生成运算树

题目

题目描述

在某种脚本语言里，有一个形如 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;
    }
};