Создание 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.

Используя это, вы можете анализировать выражение и выплевывать код при анализе выражения. Вы можете легко создать постфикс.

Если вы хотите сгенерировать префиксный код, у вас есть способ избежать выполнения вывода до тех пор, пока вы не столкнетесь с префиксной операцией. Для этого разобрать выражение и построить дерево; затем пройдите дерево в порядке префикса и выплюните результат.