是否将算术表达式树转换为没有不必要括号的字符串？
假设我构建了一个简单算术运算符的抽象语法树，比如Div(left,right), Add(left,right), Prod(left,right),Sum(left,right), Sub(left,right)。
然而，当我想要将AST转换为字符串时，我发现很难删除那些不必要的截断。
请注意，输出字符串应遵循正常的数学运算符优先顺序。
示例：
让我们将其表示为((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回答 2
Stack Overflow用户
发布于 2019-11-03 18:37:38
我在this question中找到了答案。
虽然这个问题与上面的链接有点不同，但算法仍然适用。
规则是:如果节点的子节点具有较低的优先级，则需要一对括号。如果节点的运算符是-、/、%之一，并且右操作数等于其父节点的优先级，则还需要使用括号。
我给出了伪代码(类似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
....
}
}Stack Overflow用户
发布于 2019-11-03 08:38:31
对于简单的表达式语法，可以使用运算符优先消除(大多数)多余的括号，本质上与将表达式解析为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遍历期间进行额外的检查；在检查优先级之前，您需要检查您正在访问的节点及其左侧参数是否使用了相同的运算符，其中该运算符在数学上是关联的。(这假设只有向左分组的运算符在数学上是关联的。在不太可能的情况下，您有一个向右分组的数学关联运算符，您将希望检查访问的节点及其右侧参数。)
如果满足该条件，您可以旋转AST的根，将(例如) PROD(PROD(a,b),□))转换为PROD(a,PROD(b,□))。如果a也是PROD节点，这可能会导致额外的旋转。
https://stackoverflow.com/questions/58658100
复制相似问题
腾讯云开发者
