单词和表达方式的串联

Question

简介

我正在尝试根据给定的过滤字符串创建一个字符串过滤函数（即过滤器由字符串组成） 我已经想出并编写了诸如“some+string|(test+(another|value))”这样的表达式的代码

问题

我想根据字符串中的运算符解析字符串中的表达式 我想使用两个字符作为运算符：“+”和“|”

“+”：当它出现在字符串旁边时，它应该指示它们的连接。当它与括号中的另一个表达式一起出现时，它应该表示与这些括号中的表达式的结果的串联（进一步的示例应该会变得清晰）。

“|”：应表示“逻辑或”。一个简单的例子：(a|b) = ['a', 'b']

正如我之前所说，我弄清楚了当括号中的表达式没有嵌套时如何做到这一点，现在我不知道如何实现当括号相互嵌套时获得我需要的结果

示例 1（期望的结果）

输入字符串：

((some+test)|((figure+(10|20))+(circle+figure|(3d)))+(free|frau)

输出数组：

[
    "some test free", "figure 10 circle figure free", "figure 20 circle figure free", "figure 10 3d free", "figure 20 3d free",
    "some test frau", "figure 10 circle figure frau", "figure 20 circle figure frau", "figure 10 3d frau", "figure 20 3d frau",
];

示例2

输入字符串：

"((some+test)|((figure+(10|20))+(circle+figure|(3d)))|(free|frau)"

输出数组：

[
    "some test", "figure 10 circle figure", "figure 10 3d", "figure 20 circle figure", "figure 20 3d", "free", "frau"
];

在我看来，在示例的帮助下应该清楚我想要得到什么结果。 我一直在尝试将这个任务分解为更小的任务，现在我有一个函数可以将括号中的表达式拆分为带有运算符的数组和子数组。但鉴于 + 和 | 的逻辑，我仍然无法递归处理这些数组。运营商。

我的辅助功能：

function parseLogicalExpression(expression) {
  const result = [];
  let currentExpression = '';

  for (let i = 0; i < expression.length; i++) {
    const char = expression[i];
    if (char === '(') {
      if (currentExpression !== '') {
        result.push(currentExpression);
        currentExpression = '';
      }
      let stack = 1;
      let subExpression = '';
      while (stack > 0) {
        i++;
        if (expression[i] === '(') {
          stack++;
        } else if (expression[i] === ')') {
          stack--;
        }
        if (stack > 0) {
          subExpression += expression[i];
        }
      }
      result.push(parseLogicalExpression(subExpression));
    } else if (char === '+' || char === '|') {
      if (currentExpression !== '') {
        result.push(currentExpression);
        currentExpression = '';
      }
      result.push(char);
    } else {
      currentExpression += char;
    }
  }

  if (currentExpression !== '') {
    result.push(currentExpression);
  }

  return result;
}

let expression = "((some+test)|(figure+(10|20))+(circle+figure|(3d)))"; // !!! This expression differs from that in the examples. It has been changed so that it is not too cumbersome

console.log(parseLogicalExpression(expression));

.as-console-wrapper {
  min-height: 100%;
}

Answer 1

我建议分两个阶段进行：

1. 使用 Shuntingyard 算法
构建二叉树，同时解析输入字符串
2. 从该树中生成所有字符串

这是一个实现：

class Node {
    constructor(value, left, right) {
        this.value = value;
        this.left = left;
        this.right = right;
    }
}

function parseToTree(expression) {
    const precedence = { "+": 2, "|": 1, "(": -1, ")": 0, "": 0 };
    const operators = [];
    const operands = [];
    for (const token of expression.match(/[^+|()\s]+|\S?/gs)) {
        if (token in precedence) {
            if (token !== "(") {
                while (precedence[operators.at(-1)] >= precedence[token]) {
                    if (operands.length < 2) throw new Error("Parser: Syntax error"); 
                    operands.push(new Node(operators.pop(), ...operands.splice(-2)));
                }
            }
            if (token && token !== ")") operators.push(token);
            else operators.pop(); // "("
        } else {
            operands.push(token);
        }
    }
    if (operands.length != 1) throw new Error("Parser: Syntax error");
    return operands.pop();
}

function* product(a, b, sep=" ") {
    b = [...b];
    for (const x of a) {
        for (const y of b) {
            yield x + sep + y;
        }
    }
}

function* stringsInTree(root) {
    if (typeof root === "string") {
        yield root;
    } else if (root.value === "+") {
        yield* product(stringsInTree(root.left), stringsInTree(root.right));
    } else {
        yield* stringsInTree(root.left);
        yield* stringsInTree(root.right);
    }
}

function displayStrings(expression) {
    for (const s of stringsInTree(parseToTree(expression))) {
        console.log(s);
    }
}

// demo: example 2
displayStrings("(some+test)|((figure+(10|20))+(circle+figure|(3d)))|(free|frau)");