表达式树的问题
表达式树的问题
提问于 2019-03-04 08:21:52
我目前正在尝试找出一个表达式树的算法。我当前获得的字符串将类似于Hello+12+World或A2-12-A3-14。字符串中将包含相同的运算符。由于我的算法当前没有将最后一个操作数放入树中。我已经在网上看过了，我很难理解如何让它正常工作。
Stack<BaseNode> TreeStack = new Stack<BaseNode>();
BaseNode temp1 = new BaseNode();
BaseNode temp2 = new BaseNode();
for (int i = 0; i < tree.Length; i++)
{
VariableNode varNode = new VariableNode();
NumericalNode numNode = new NumericalNode();
if (CheckExpressions(tree[i])) // if the character is an operator
{
OperatorNode expression = new OperatorNode(tree[i]);
temp1 = TreeStack.Pop();
if (TreeStack.Count != 0)
{
temp2 = TreeStack.Pop();
}
expression.Right = temp1;
expression.Left = temp2;
TreeStack.Push(expression);
}
else if (!CheckExpressions(tree[i]))
{
if (Char.IsLetter(tree[i]))
{
while (Char.IsLetter(tree[i])) // for the variable node
{
varNode.name += tree[i];
if (i + 1 == tree.Length)
{
break;
}
i++;
}
TreeStack.Push(varNode);
if (i + 1 != tree.Length)
{
i--;
}
}
else if (Char.IsDigit(tree[i])) // for constant value
{
int zero = 0; // for appending the numbers to combine them
while (Char.IsDigit(tree[i]))
{
if (zero == 0)
{
zero = tree[i] - '0';
}
else
{
zero = int.Parse(zero.ToString() + tree[i].ToString());
}
if (i < tree.Length)
{
i++;
}
}
if (i + 1 != tree.Length)
{
i--;
}
numNode.number = zero;
TreeStack.Push(numNode);
}
}
}回答 1
Stack Overflow用户
发布于 2019-03-04 09:09:26
我想你知道你错过了第二个操作数，因为一旦你看到一个操作符，你就会尝试弹出2个值的堆栈。在示例中，您可以很容易地看到它永远不会是这种情况(堆栈将有2个变量，因为运算符是二进制的)。所以你应该知道如何存储第二个变量和运算符，并在以后的某个时刻尝试计算它。下面的算法可能会有帮助，但要理解这是一个简单操作符的基本算法。
- 从两个堆栈开始，一个是变量，另一个是运算符。
- 在将运算符推送到运算符堆栈之前，请检查优先级/优先级。如果堆栈顶部的现有运算符的优先级高于或等于您将要推送的运算符和变量的优先级，则开始弹出堆栈。
- 最后，当你遍历完整个字符串之后，检查堆栈中是否有留下的运算符，完成对它的求值，就应该得到最终结果。
在2*3+4中，当达到+时，一个堆栈中会有2,3，另一个堆栈中会有*。现在尝试push +，你会看到堆栈中现有的*具有更高的优先级，所以将它弹出，因为它是一个二元运算符弹出2个变量，构建一个表达式evaluate它并在变量栈上push (因为计算的结果将是一个变量/数字)，然后再次查看堆栈上是否有更多具有更高优先级的运算符。
添加解决方案时，请记住: 1.运算符优先级/哪种运算符(一元/二元)/是否对称/非对称(+是对称的，但幂不是)将发挥重要作用。
尽量不要在循环中修改i变量，迟早你会遇到麻烦的。
给定的代码仅适用于给定的2个示例，检查优先级的部分为空，但可以在现有代码的基础上填充。
你将需要修改你的变量命名逻辑，如果有像'A2‘这样的混合名称，你当前的逻辑将会失败。
string tree = "AB-12-AC-14";
Stack<BaseNode> TreeStack = new Stack<BaseNode>();
Stack<BaseNode> TreeStack1 = new Stack<BaseNode>();
BaseNode temp1 = new BaseNode();
BaseNode temp2 = new BaseNode();
for (int i = 0; i < tree.Length; i++)
{
VariableNode varNode = new VariableNode();
NumericalNode numNode = new NumericalNode();
if (CheckExpressions(tree[i])) // if the character is an operator
{
OperatorNode expression = new OperatorNode(tree[i]);
//check priority should pass the current operator to really check for priority
if (CheckPriority() || TreeStack1.Count == 0)
{
TreeStack1.Push(expression);
}
else
{
// assuming binary operators only
temp1 = TreeStack.Pop();
temp2 = TreeStack.Pop();
expression.Right = temp1;
expression.Left = temp2;
TreeStack.Push(expression);
// need to check if there are more operators on stack1 are they higher priority then current operator
// if they are then pop them and apply them too
}
}
else if (!CheckExpressions(tree[i]))
{
if (Char.IsLetter(tree[i]))
{
while (Char.IsLetter(tree[i])) // for the variable node
{
varNode.name += tree[i];
if (i + 1 == tree.Length)
{
break;
}
i++;
}
TreeStack.Push(varNode);
if (i + 1 != tree.Length)
{
i--;
}
}
else if (Char.IsDigit(tree[i])) // for constant value
{
int zero = 0; // for appending the numbers to combine them
while (i < tree.Length && Char.IsDigit(tree[i])) // need to check for length otherwise index will go out of bounds
{
if (zero == 0)
{
zero = tree[i] - '0';
}
else
{
zero = int.Parse(zero.ToString() + tree[i].ToString());
}
if (i < tree.Length)
{
i++;
}
}
if (i + 1 != tree.Length)
{
i--;
}
numNode.number = zero;
TreeStack.Push(numNode);
}
}
}
// finish any remaining operators and push the final expression on the stack
while (TreeStack1.Count!=0)
{
OperatorNode expression1 = new OperatorNode(((OperatorNode)TreeStack1.Pop()).v);
expression1.Right = TreeStack.Pop();
expression1.Left = TreeStack.Pop();
TreeStack.Push(expression1);
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/54975166
复制相关文章
相似问题