java - Converting tree representing math expression to a string without redundant parentheses
问题描述
I want to convert a tree that represents a math expression into the actual math expression (a string like "a+b/c"
)
The tree representation is the simplest you could imagine:
A+B/C
would be this tree:
OperationNode(+, A, OperationNode(/, B, C))
And (A+B)/C
would be this tree:
OperationNode(/, OperationNode(+, A, B), C)
In order to convert the tree into the string, I'm using the Visitor pattern. The problem comes with parentheses.
My current Visitor implementation ALWAYS adds parentheses to the nodes, so every tree I generate turns into a string like this:
(((A+B)+C)+D)
Notice the redundant parentheses.
So the question is: how could I make my Visitor generate the string with no redundant parentheses?
解决方案
正如 NelFeal 在遍历树时所写的那样,您只需要检查子操作的优先级是否小于当前操作的优先级。
我为您实现了访问者模式,希望对您有所帮助。
enum Operation
{
Add,
Multiply,
Power,
UnaryMinus,
None,
}
static class OperationExtensions
{
public static string ToFriendlyString(this Operation me)
{
switch (me)
{
case Operation.None:
return "";
case Operation.Add:
return "+";
case Operation.Multiply:
return "*";
case Operation.Power:
return "^";
case Operation.UnaryMinus:
return "-";
default:
throw new ArgumentException();
}
}
}
class OperationNode
{
public Operation Op;
public OperationNode(Operation op)
{
Op = op;
}
}
interface IVisitor
{
void Visit(OperationNodeLeaf node);
void Visit(OperationNode1 node);
void Visit(OperationNode2 node);
}
sealed class Visitor : IVisitor
{
public string Text { get; set; }
private void Enclose(OperationNode subNode, Operation op)
{
if (subNode.Op < op)
{
Text = Text + "(";
Visit((dynamic)subNode);
Text = Text + ")";
}
else
{
Visit((dynamic)subNode);
}
}
public void Visit(OperationNodeLeaf node)
{
Text = Text + node.Op.ToFriendlyString();
Text = Text + node.Value.ToString();
}
public void Visit(OperationNode1 node)
{
Text = Text + node.Op.ToFriendlyString();
Enclose(node.SubNode, node.Op);
}
public void Visit(OperationNode2 node)
{
Enclose(node.LeftSubNode, node.Op);
Text = Text + node.Op.ToFriendlyString();
Enclose(node.RightSubNode, node.Op);
}
}
class OperationNodeLeaf : OperationNode
{
public int Value;
public OperationNodeLeaf(int v, Operation op = Operation.None) : base(op)
{
Value = v;
}
void Accept(IVisitor v)
{
v.Visit(this);
}
}
class OperationNode1 : OperationNode
{
public OperationNode SubNode;
public OperationNode1(OperationNode sn, Operation op) : base(op)
{
SubNode = sn;
}
void Accept(IVisitor v)
{
v.Visit(this);
}
}
class OperationNode2 : OperationNode
{
public OperationNode LeftSubNode;
public OperationNode RightSubNode;
public OperationNode2(OperationNode lsn, OperationNode rsn, Operation op) : base(op)
{
LeftSubNode = lsn;
RightSubNode = rsn;
}
void Accept(IVisitor v)
{
v.Visit(this);
}
}
class Program
{
static void Main(string[] args)
{
var tree =
new OperationNode2(
new OperationNode2(
new OperationNode2(new OperationNodeLeaf(5), new OperationNodeLeaf(6), Operation.Add),
new OperationNode2(new OperationNodeLeaf(5), new OperationNodeLeaf(6), Operation.Multiply),
Operation.Power
),
new OperationNode2(
new OperationNode2(new OperationNodeLeaf(1), new OperationNodeLeaf(2), Operation.Multiply),
new OperationNode1(new OperationNodeLeaf(7, Operation.None), Operation.UnaryMinus),
Operation.Add
),
Operation.Multiply
);
var visitor = new Visitor();
visitor.Visit(tree);
System.Diagnostics.Debug.WriteLine(visitor.Text);
}
}
(5+6)^(5*6)*(1*2+-7)
推荐阅读
- java - OnOptionsItemSelected - 按下一个按钮执行另一个按钮的操作
- angular - 使用 jasmine-marbles 的 takeUntil-using NGRX 效果测试未按预期完成
- node.js - Auth0 NodeJS JWT 身份验证在移动应用程序的 API 中
- javascript - 打字稿:从动态创建的对象中推断出确切的值
- python - 如何使用 TensorFlow 计算平均精度(mAP)?
- javascript - 如何限制数字字段在 oracle apex 中仅输入数字
- reactjs - 突变后重新获取查询不起作用
- ruby-on-rails - 如何使用 simple_form 在 Rails 中向数据库提交表单?
- c - CTypes 的问题 - 调用 C dll 函数
- cassandra - Cassandra 在 GCP 上通过 VPN 进行 DC 间同步