在没有不必要的括号的情况下将算术表达式树转换为字符串？

Question

假设我构建了一个简单算术运算符的抽象语法树，例如 Div(left,right), Add(left,right), Prod(left,right),Sum(left,right), Sub(left,right)。

然而当我想将AST转换为字符串时，我发现很难去除那些不必要的parathesis。

注意输出字符串应遵循正常的数学运算符优先级。

示例：

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

对于简单的表达式语法，您可以使用运算符优先级消除（大部分）冗余括号，这与将表达式解析为 AST 的方式基本相同。

如果您正在查看 AST 中的节点，您需要做的就是将节点运算符的优先级与参数运算符的优先级进行比较，在以下情况下使用运算符的关联性优先级是平等的。如果节点的运算符优先级高于参数，则参数不需要用括号括起来；否则它需要它们。（这两个参数需要单独检查。）如果一个参数是文字或标识符，那么当然不需要括号；通过使此类值的优先级无限（或至少大于任何运算符优先级），可以轻松处理这种特殊情况。

但是，您的示例包含另一个基于运算符的数学结合性来消除冗余括号的建议。不幸的是，数学结合律并不总是适用于计算机程序。如果您的表达式涉及浮点数，例如 a+(b+c) 和 (a+b)+c 可能具有非常不同的值：

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

出于这个原因，编译器避免重新排列乘法和加法的应用顺序是很常见的，至少对于浮点运算，对于检查整数溢出的语言的整数运算也是如此。

但是如果你真的想根据数学关联性重新排列，你需要在 AST 的遍历过程中进行额外的检查；在检查优先级之前，您需要检查您正在访问的节点及其左参数是否使用相同的运算符，该运算符已知在数学上是关联的。（这假设只有分组到左边的运算符在数学上是关联的。在不太可能的情况下，你有一个分组到右边的数学关联运算符，你会想要检查访问的节点及其右边的参数。）

如果满足该条件，您可以旋转 AST 的根，将（例如）PROD(PROD(a,b),□)) 变成 PROD(a,PROD(b,□))。在 a 也是一个 PROD 节点的情况下，这可能会导致额外的旋转。

Answer 2

我在this question中找到了答案。

虽然题目和上面的link有点不同，但是算法还是适用的

规则是：如果节点的子节点优先级较低，则需要一对括号。如果节点的运算符是-、/、%之一，且右操作数等于其父节点的优先级，也需要括号。

我给伪代码（类似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
      ....    
    }
  }

在没有不必要的括号的情况下将算术表达式树转换为字符串？

Convert Arithmetic Expression Tree to string without unnecessary parenthesis?

tree

parsing

abstract-syntax-tree