bod*_*ydo 6 evaluation parsing tokenize
我正在学习如何编写标记器,解析器以及作为练习我正在用JavaScript编写计算器.
我正在使用一种prase树方法(我希望我的这个术语正确)来构建我的计算器.我正在根据运算符优先级构建一个令牌树.
例如,给定一个表达式a*b+c*(d*(g-f)),正确的树将是:
+
/ \
* \
/ \ \
a b \
*
/ \
c *
/ \
d -
/ \
g f
一旦我拥有树,我就可以遍历它并递归地在左右节点的每个根节点上应用操作以找到表达式的值.
然而,最大的问题是实际构建这棵树.我只是无法弄清楚如何正确地做到这一点.我不能只拆分运营商+,-,/和*和,因为优先的左侧和右侧部分创建树.
到目前为止我所做的是将表达式标记化.所以a*b+c*(d*(g-f)),我给出了一系列令牌:
[a, Operator*, b, Operator+, c, Operator*, OpenParen, d, Operator*, OpenParen, g, Operator-, f, CloseParen, CloseParen]
但是我无法弄清楚如何从这个令牌数组转到我可以遍历并找出值的树的下一步.任何人都可以帮我提出如何做到这一点的想法吗？
小智 7
对了，我不知道如何让它看起来漂亮
我用 C 语言编写了一个类似的程序，但我的树是颠倒的，这意味着新的运算符成为根。
C 代码中的计算器解析树，但请阅读自述文件
例如：输入 2 + 3 - 4
从空节点开始
{}
规则 1：当您读取一个数字时，在当前节点的左侧或右侧添加一个子节点，以空节点为准
{}
/
{2}
规则2：然后你读取一个运算符，你必须从当前节点{2}开始爬到一个空节点，当找到一个时，将其值更改为+，如果没有空节点，则必须创建一个然后使它是树的根
{+}
/
{2}
你遇到另一个数字，转到规则 1，我们目前在 {+} 找到一个空的边（这次是对的）
{+}
/ \
{2} {3}
现在我们有了新的操作数“-”，但由于 {3} 的父节点已满，因此您必须创建新节点并使其成为所有节点的根
{-}
/
{+}
/ \
{2} {3}
哦，看看那个，另一个数字，因为我们当前指向根，让我们找到一个空的 {-} 子代，（提示右侧）
{-}
/ \
{+} {4}
/ \
{2} {3}
构建树后，看一下函数 getresult() 来计算所有内容
您可能想知道括号是如何工作的。我是这样做的：
每次遇到“(”时，我都会创建全新的树，并将其余输入构建到该树中。如果我读到另一个“(”，我会创建另一个树并继续使用新树进行构建。
读取输入后，我将所有树的根相互连接以形成一棵最终的树。查看代码和自述文件，我必须画图来解释一切。
希望这也能帮助未来的读者
我经常看到这个问题，所以我就把这个写下来。这肯定会推动您走向正确的方向，但要小心，这是一个自上而下的解析器，因此它可能不会按照您期望的优先级解释表达式。
class Program
{
static void Main()
{
Console.WriteLine(SimpleExpressionParser.Parse("(10+30*2)/20").ToString());
Console.ReadLine();
//
// ouput: ((10+30)*2)/20
}
public static class SimpleExpressionParser
{
public static SimpleExpression Parse(string str)
{
if (str == null)
{
throw new ArgumentNullException("str");
}
int index = 0;
return InternalParse(str, ref index, 0);
}
private static SimpleExpression InternalParse(string str, ref int index, int level)
{
State state = State.ExpectLeft;
SimpleExpression _expression = new SimpleExpression();
int startIndex = index;
int length = str.Length;
while (index < length)
{
char chr = str[index];
if (chr == ')' && level != 0)
{
break;
}
switch (state)
{
case State.ExpectLeft:
case State.ExpectRight:
{
SimpleExpression expression = null;
if (Char.IsDigit(chr))
{
int findRep = FindRep(Char.IsDigit, str, index + 1, length - 1);
expression = new SimpleExpression(int.Parse(str.Substring(index, findRep + 1)));
index += findRep;
}
else if (chr == '(')
{
index++;
expression = InternalParse(str, ref index, level + 1);
}
if (expression == null)
{
throw new Exception(String.Format("Expression expected at index {0}", index));
}
if (state == State.ExpectLeft)
{
_expression.Left = expression;
state = State.ExpectOperator;
}
else
{
_expression.Right = expression;
state = State.ExpectFarOperator;
}
}
break;
case State.ExpectOperator:
case State.ExpectFarOperator:
{
SimpleExpressionOperator op;
switch (chr)
{
case '+': op = SimpleExpressionOperator.Add; break;
case '-': op = SimpleExpressionOperator.Subtract; break;
case '*': op = SimpleExpressionOperator.Multiply; break;
case '/': op = SimpleExpressionOperator.Divide; break;
default:
throw new Exception(String.Format("Invalid operator encountered at index {0}", index));
}
if (state == State.ExpectOperator)
{
_expression.Operator = op;
state = State.ExpectRight;
}
else
{
index++;
return new SimpleExpression(op, _expression, InternalParse(str, ref index, level));
}
}
break;
}
index++;
}
if (state == State.ExpectLeft || state == State.ExpectRight)
{
throw new Exception("Could not complete expression");
}
return _expression;
}
private static int FindRep(Func<char, bool> validator, string str, int beginPos, int endPos)
{
int pos;
for (pos = beginPos; pos <= endPos; pos++)
{
if (!validator.Invoke(str[pos]))
{
break;
}
}
return pos - beginPos;
}
private enum State
{
ExpectLeft,
ExpectRight,
ExpectOperator,
ExpectFarOperator
}
}
public enum SimpleExpressionOperator
{
Add,
Subtract,
Multiply,
Divide
}
public class SimpleExpression
{
private static Dictionary<SimpleExpressionOperator, char> opEquivs = new Dictionary<SimpleExpressionOperator, char>()
{
{ SimpleExpressionOperator.Add, '+' },
{ SimpleExpressionOperator.Subtract, '-' },
{ SimpleExpressionOperator.Multiply, '*' },
{ SimpleExpressionOperator.Divide, '/' }
};
public SimpleExpression() { }
public SimpleExpression(int literal)
{
Literal = literal;
IsLiteral = true;
}
public SimpleExpression(SimpleExpressionOperator op, SimpleExpression left, SimpleExpression right)
{
Operator = op;
Left = left;
Right = right;
}
public bool IsLiteral
{
get;
set;
}
public int Literal
{
get;
set;
}
public SimpleExpressionOperator Operator
{
get;
set;
}
public SimpleExpression Left
{
get;
set;
}
public SimpleExpression Right
{
get;
set;
}
public override string ToString()
{
StringBuilder sb = new StringBuilder();
AppendExpression(sb, this, 0);
return sb.ToString();
}
private static void AppendExpression(StringBuilder sb, SimpleExpression expression, int level)
{
bool enclose = (level != 0 && !expression.IsLiteral && expression.Right != null);
if (enclose)
{
sb.Append('(');
}
if (expression.IsLiteral)
{
sb.Append(expression.Literal);
}
else
{
if (expression.Left == null)
{
throw new Exception("Invalid expression encountered");
}
AppendExpression(sb, expression.Left, level + 1);
if (expression.Right != null)
{
sb.Append(opEquivs[expression.Operator]);
AppendExpression(sb, expression.Right, level + 1);
}
}
if (enclose)
{
sb.Append(')');
}
}
}
}