作者热门文章
- c - 在位数组中找到第一个零
- linux - Unix 显示有关匹配两种模式之一的文件的信息
- 正则表达式替换多个文件
- linux - 隐藏来自 xtrace 的命令
我们使用 Shunting-Yard 算法来评估表达式。我们可以通过简单地应用算法来验证表达式。如果缺少操作数、未匹配的括号和其他内容,它将失败。然而,调车场算法具有比人类可读的中缀更大的支持语法。例如,
1 + 2
+ 1 2
1 2 +
是提供“1+2”作为调车场算法输入的所有可接受方式。 '+ 1 2' 和 '1 2 +' 不是有效的中缀,但标准的 Shunting-Yard 算法可以处理它们。该算法并不真正关心顺序,它按优先顺序应用运算符以获取“最近”的操作数。
我们希望将我们的输入限制为有效的人类可读中缀。我正在寻找一种方法来修改 Shunting-Yard 算法使其因无效中缀而失败,或者在使用 Shunting-Yard 之前提供中缀验证。
有人知道任何已发布的技术可以做到这一点吗?我们必须同时支持基本运算符、自定义运算符、括号和函数(具有多个参数)。除了基本的在线运算符之外,我还没有看到任何可以使用的东西。
谢谢
最佳答案
我的问题的解决方案是增强发布在 Wikipedia 上的算法与 state machine recommended by Rici .我在这里发布伪代码,因为它可能对其他人有用。
Support two states, ExpectOperand and ExpectOperator.
Set State to ExpectOperand
While there are tokens to read:
If token is a constant (number)
Error if state is not ExpectOperand.
Push token to output queue.
Set state to ExpectOperator.
If token is a variable.
Error if state is not ExpectOperand.
Push token to output queue.
Set state to ExpectOperator.
If token is an argument separator (a comma).
Error if state is not ExpectOperator.
Until the top of the operator stack is a left parenthesis (don't pop the left parenthesis).
Push the top token of the stack to the output queue.
If no left parenthesis is encountered then error. Either the separator was misplaced or the parentheses were mismatched.
Set state to ExpectOperand.
If token is a unary operator.
Error if the state is not ExpectOperand.
Push the token to the operator stack.
Set the state to ExpectOperand.
If the token is a binary operator.
Error if the state is not ExpectOperator.
While there is an operator token at the top of the operator stack and either the current token is left-associative and of lower then or equal precedence to the operator on the stack, or the current token is right associative and of lower precedence than the operator on the stack.
Pop the operator from the operator stack and push it onto the output queue.
Push the current operator onto the operator stack.
Set the state to ExpectOperand.
If the token is a Function.
Error if the state is not ExpectOperand.
Push the token onto the operator stack.
Set the state to ExpectOperand.
If the token is a open parentheses.
Error if the state is not ExpectOperand.
Push the token onto the operator stack.
Set the state to ExpectOperand.
If the token is a close parentheses.
Error if the state is not ExpectOperator.
Until the token at the top of the operator stack is a left parenthesis.
Pop the token off of the operator stack and push it onto the output queue.
Pop the left parenthesis off of the operator stack and discard.
If the token at the top of the operator stack is a function then pop it and push it onto the output queue.
Set the state to ExpectOperator.
At this point you have processed all the input tokens.
While there are tokens on the operator stack.
Pop the next token from the operator stack and push it onto the output queue.
If a parenthesis is encountered then error. There are mismatched parenthesis.
通过查看前面的记号,您可以轻松区分一元运算符和二元运算符(我特别指的是否定前缀和减法运算符)。如果没有前一个标记,前一个标记是一个左括号,或者前一个标记是一个运算符,那么你遇到的是一元前缀运算符,否则你遇到的是二元运算符。
关于c# - 调车场验证表达式,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/29634992/
我是一名优秀的程序员,十分优秀!