javaScript：表达式转二叉树

以前学习数据结构的时候，学过将数学表达式（中缀表达式）转换为二叉树，最近遇到需要将带有逻辑与和逻辑或的表达式转换为树结构的需求，参考了一些博客，最后做出来效果如下：

表达式：

(1 & 2) &3 | 4

树结构：

对树结构进行中序遍历就能还原为原表达式。

下面是处理过程：

1、中缀表达式转后缀表达式

主要逻辑：

准备一个栈用来暂存操作数和运算符，准备一个队列用来存储后缀表达式。

从左向右开始读取算术表达式的元素X，分以下情况进行不同的处理：

（1）如果X是操作数，直接入队（即直接放入表达式中）

（2）如果X是运算符：再分以下情况：

​ 1）如果栈为空，直接入栈。

​ 2）如果X==”（“，直接入栈。

​ 3）如果X==”）“，则将栈里的元素逐个出栈并入队，直到遇到”）”。注意：”）“和”（“都出栈但不入队。

​ 4）如果是其他运算符，若X优先级小于栈顶元素，则出栈并入队直到X大于栈顶元素。否则直接入栈。

原文链接：https://blog.csdn.net/DH2442897094/article/details/82760498

本文中的表达式只包含数字以及逻辑与、逻辑或运算符，已知逻辑与的优先级大于逻辑或。

原表达式：(1 & 2) &3 | 4

代码如下：

  const getString = (str) => {
    //去掉表达式中可能出现的空格
    str = str.replace(//s*/g, "");
    //当表达式只有一个操作数时不做处理
    if (str.length < 2) {
      return;
    }
    let opStack = []; //暂存栈
    let string = ""; //后缀表达式队列
    //对str中的字符逐个读取
    str.split("").forEach((item) => {
      //isNaN方法判断字符是否是非数字，非数字返回true，数字返回false
      if (!isNaN(item)) {
        //若是操作数，直接入队
        string += item;
      } else {
        //遇到"("直接入栈
        if (item === "(") {
          opStack.push(item);
        } else if (item === ")") {
          //遇到")"出栈并入队直到遇到"("
          for (let i = opStack.length - 1; i >= 0; i--) {
            const key = opStack.pop();
            if (key === "(") {
              break;
            }
            //入队在判断"("之前，因为"("不入队
            string += key;
          }
        } else {
          //其他操作符，判断优先级
          let result = checkOp(item, opStack, string);
          opStack = result.stack;
          string = result.string;
        }
      }
    });
    //原表达式读取后若栈中还有元素，则逐个出栈并入队
    opStack.forEach(() => {
      string += opStack.pop();
    });
  };

  //判断优先级
  const checkOp = (op, stack, string) => {
    //若该操作符优先级小于栈顶操作符（只能是|与&相比较的情况）
    if (op === "|" && stack[stack.length - 1] === "&") {
      //出栈并入队
      string += stack.pop();
      //再与栈顶元素判断优先级
      checkOp(op, stack, string);
    } else {
      stack.push(op);
    }
    //返回处理后的栈和表达式
    return { stack: stack, string: string };
  };

处理后得到的string就是目的后缀表达式：12&3&4|

2、对后缀表达式构造树结构

主要逻辑：

准备一个栈用来存放子节点。

对后缀表达式从左往右读取元素i，分以下情况对i做处理：

1、i是数字，直接入栈。

2、i是操作符，取栈顶两个元素作为i的子节点，将i入栈。

后缀表达式读取结束后，栈内还剩一个元素，该元素就是我们要的数组。

代码如下：

  const buildTree = (str) => {
    let children = [];
    //用到前端树控件，需要唯一id，可忽略
    let index = 0;
    str.split("").forEach((item) => {
      //数字直接入栈，用到前端控件需要显示label，不需要的直接push(item)即可
      if (!isNaN(item)) {
        children.push({
          id: index++,
          value: item,
          label: item,
        });
      } else {
        //遇到操作数，取栈顶两个元素作为子节点
        const parent = {
          id: index++,
          value: item,
          label: item,
          children: children.splice(children.length - 2).reverse(),
        };
        //处理后入栈
        children.push(parent);
      }
    });
    console.log(children);
    //控件的绑定值
    setOptions(children);
  };

处理后的children就是我们要的数组，是一个二叉树结构。

这里我用到了MUI的TreeItem控件，前端展示效果为：