时间戳

首页 > 解决方案 > 将算术表达式树转换为字符串而没有不必要的括号？

parsing - 将算术表达式树转换为字符串而没有不必要的括号？

问题描述

假设我构建了一个简单算术运算符的抽象语法树，例如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

标签： parsingtreeabstract-syntax-tree

解决方案

我在这个问题中找到了答案。

尽管问题与上面的链接有点不同，但该算法仍然适用。

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

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

推荐阅读