Given a binary expression syntax tree, serialize it into an infix string using the minimum number of parentheses required to preserve the tree's evaluation semantics.
Each node is one of:
-
A variable leaf, represented by a non-empty identifier such as
a
,
x
, or
foo
-
A binary operator node whose operator is one of
+
,
-
,
*
,
/
and whose left and right children are valid expression nodes
Use standard arithmetic precedence:
-
*
and
/
have higher precedence than
+
and
-
-
Operators are evaluated left to right when precedence is the same
Return a string representation of the expression with unnecessary parentheses removed, but do not change the meaning of the original expression tree.
Examples:
-
Tree for
(a + b) * c
should serialize as
(a+b)*c
-
Tree for
a + (b * c)
should serialize as
a+b*c
-
Tree for
a - (b + c)
should serialize as
a-(b+c)
-
Tree for
(a - b) - c
should serialize as
a-b-c
-
Tree for
a / (b * c)
should serialize as
a/(b*c)
Implement a function such as:
string serialize(Node root)
where Node contains either a variable name or an operator with left and right children.