Преобразовать дерево арифметических выражений в строку без лишних скобок?

Question

Предположим, я строю абстрактное синтаксическое дерево из простых арифметических операторов, таких как Div(left,right), Add(left,right), Prod(left,right),Sum(left,right), Sub(left,right).

Однако, когда я хочу преобразовать AST в строку, я обнаружил, что эти ненужные паратезы трудно удалить.

Обратите внимание, что выходная строка должна соответствовать обычному приоритету математического оператора.

Примеры:

Prod(Prod(1,2),Prod(2,3)) давайте обозначим это как ((1*2)*(2,3)) в строке, это должно быть 1*2*2*3

больше примеров:

(((2*3)*(3/5))-4) ==> 2*3*3/5 - 4

(((2-3)*((3*7)/(1*5))-4) ==> (2-3)*3*7/(1*5) - 4

(1/(2/3))/5 ==> 1/(2/3)/5 

((1/2)/3))/5 ==> 1/2/3/5

((1-2)-3)-(4-6)+(1-3) ==> 1-2-3-(4-6)+1-3

Answer 1

Я найду ответ в на этот вопрос .

Хотя вопрос немного отличается от ссылки выше, алгоритм все еще применяется.

Правило: если дочерние элементы узла имеют более низкий приоритет, тогда необходима пара круглых скобок. Если оператор узла один из -, /, % и если правый операнд равен приоритету родительского узла, ему также требуется скобка.

Я даю псевдокод (scalaкак код) удар:

def toString(e:Expression, parentPrecedence:Int = -1):String = {

    e match {

      case Sub(left2,right2) =>
        val p = 10
        val left = toString(left2, p)
        val right = toString(right, p + 1) // +1 !!
        val op = "-"
        lazy val s2 = left :: right :: Nil mkString op
        if (parentPrecedence > p )
          s"($s2)"
        else s"$s2"

      //case Modulus and divide is similar to Sub except for p

      case Sum(left2,right2) =>
        val p = 10
        val left = toString(left2, p)
        val right = toString(right, p) //
        val op = "-"
        lazy val s2 = left :: right :: Nil mkString op
        if (parentPrecedence > p )
          s"($s2)"
        else s"$s2"

      //case Prod is similar to Sum
      ....    
    }
  }

Answer 2

Для простой грамматики выражений вы можете устранить (большинство) избыточных скобок, используя приоритет оператора, по сути, так же, как вы анализируете выражение в AST.

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

Однако в вашем примере есть еще одно предложение по исключению избыточных скобок, основанное на математической ассоциативностиОператор. К сожалению, математическая ассоциативность не всегда применима в компьютерной программе. Если ваши выражения с числами с плавающей запятой, например, a+(b+c) и (a+b)+c, могут иметь очень разные значения:

(gdb) p (1000000000000000000000.0 + -1000000000000000000000.0) + 2
$1 = 2
(gdb) p 1000000000000000000000.0 + (-1000000000000000000000.0 + 2)
$2 = 0

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

Но если вы действительно хотите переставить на основе математической ассоциативности, вам понадобитсядополнительная проверка во время прогулки по АСТ;перед проверкой приоритета вы захотите проверить, использует ли посещаемый вами узел и его левый аргумент тот же оператор, где этот оператор математически ассоциативен. (Это предполагает, что только операторы, которые группируются слева, являются математически ассоциативными. В маловероятном случае, если у вас есть математически ассоциативный оператор, который группирует справа, вы захотите проверить посещаемый узел и его правый аргумент.)

Если это условие выполнено, вы можете повернуть корень AST, превратив (например) PROD(PROD(a,b),□)) в PROD(a,PROD(b,□)). Это может привести к дополнительным поворотам в случае, если a также является PROD узлом.