Csharp/C#教程:Shunting-Yardvalidation表达式分享


Shunting-Yardvalidation表达式

我们使用Shunting-Yard算法来计算表达式。 我们可以通过简单地应用算法来validation表达式。 如果缺少操作数,错过匹配的括号和其他内容,它将失败。 然而,Shunting-Yard算法具有比人类可读中缀更大的支持语法。 例如,

1 + 2 + 1 2 1 2 + 

是提供“1 + 2”作为Shunting-Yard算法输入的可接受方法。 ‘+ 1 2’和’1 2 +’不是有效的中缀,但标准的Shunting-Yard算法可以处理它们。 该算法并不真正关心顺序,它通过优先顺序抓取“最近”的操作数来应用运算符。

我们希望将输入限制为有效的人类可读中缀。 我正在寻找一种方法来修改Shunting-Yard算法以使用无效的中缀失败,或者在使用Shunting-Yard之前提供中缀validation。

有人知道任何已发表的技术吗? 我们必须支持基本运算符,自定义运算符,括号和函数(带有多个参数)。 我没有看到任何与在线基本操作员相关的东西。

谢谢

我的问题的解决方案是使用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. 

通过查看前一个标记,您可以轻松区分一元和二元运算符(我具体说的是负前缀和减法运算符)。 如果没有先前的令牌,则前一个令牌是开括号,或者前一个令牌是运算符,那么您遇到了一元前缀运算符,否则您遇到了二元运算符。

关于Shunting Yard算法的一个很好的讨论是https://www.engr.mun.ca/~theo/Misc/exp_parsing.htm那里提出的算法使用了运算符堆栈的关键思想,但有一些语法知道应该预期什么下一个。 它有两个主要函数E() ,它们需要一个表达式, P()期望一个前缀运算符,一个变量,一个数字,括号和函数。 前缀运算符总是绑定比二元运算符更紧密,所以你想先处理它。

如果我们说P代表一些前缀序列而B是二元运算符,那么任何表达式都是forms

 PBPBP 

即你要么是期待一个前缀序列,要么是一个二元运算符。 正式的语法是

 E -> P (BP)* 

和P将是

 P -> -P | variable | constant | etc. 

这转换为psudocode as

 E() { P() while next token is a binary op: read next op push onto stack and do the shunting yard logic P() if any tokens remain report error pop remaining operators off the stack } P() { if next token is constant or variable: add to output else if next token is unary minus: push uminus onto operator stack P() } 

您可以扩展它以处理其他一元运算符,函数,括号,后缀运算符。

上述就是C#学习教程:Shunting-Yardvalidation表达式分享的全部内容,如果对大家有所用处且需要了解更多关于C#学习教程,希望大家多多关注—计算机技术网(www.ctvol.com)!

本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。

ctvol管理联系方式QQ:251552304

本文章地址:https://www.ctvol.com/cdevelopment/983735.html

(0)
上一篇 2021年12月19日
下一篇 2021年12月19日

精彩推荐