从逻辑表达式创建AST

Question

我想改信

((a v b) ^ c) v e -> c

转到

[
    'implication'
    [
        'or',
        [
            'and',
            [
                'or',
                'a',
                'b'
            ],
            'c'
        ],
        'e'
    ],
    'c'
]

这怎麽可能？

我想我应该从定义一些运算符开始(运算符类型对应于运算符符号)

var operators = {
  'v' : 'or',
  '^' : 'and',
  '->': 'implication'
};

然后遍历字符串

// string
var infix = '((a v b) ^ c) v e -> c';

// remove spaces, so infix[i]!=" "
infix = infix.replace(/\s+/g, '');

// traverse through string
for (let i=0; i<infix.length; i++) {
  // get token
  var token = infix[i];

  // if token is an operator
  if (operators.indexOf(token) !== -1) {
    (...)
  }
  // if token is parenthesis
  else if (token === '(') {
    (...)
  }

  (...)
}

但我不知道如何走得更远。

我猜树形结构数组将使用下面的内容来完成

expression = [operators[token], expression];

因此，表达式被保留，但在数组中处于嵌套级别。

Answer 1

参见my SO answer on how to write a parser。

使用它，您可以解析表达式，并在解析表达式时输出代码。您可以通过这种方式轻松地生成postfix。

如果您希望生成前缀代码，那么至少在遇到前缀操作之前，您有一种方法可以避免执行输出。为此，解析表达式并构建树；然后按前缀顺序遍历树并输出结果。