分流-场验证表达式
我们使用分流-场算法来计算表达式。我们可以简单地应用该算法来验证该表达式。如果缺少操作数、错匹配括号和其他内容，则会失败。然而，分流-场算法有一个更大的支持语法，而不仅仅是人类可读的内插即用。例如,
1 + 2
+ 1 2
1 2 +是提供“1+2”作为分流-场算法输入的所有可接受的方法。“+12”和“12+”是无效的，但是标准的分流场算法可以处理它们。该算法并不真正关心这个顺序，它通过优先抓取‘最近’操作数的顺序应用运算符。
我们希望将输入限制为有效的人类可读的infix。我正在寻找一种方法，要么修改分流-场算法，以失败与无效的修正，或提供一个修正验证之前，使用分流场。
是否有人知道任何公开发表的技术来做到这一点？我们必须同时支持基本运算符、自定义运算符、括号和函数(带有多个参数)。我还没见过比在线基本运营者更有效的东西。
谢谢
回答 2
Stack Overflow用户
发布于 2015-04-15 13:50:43
解决我的问题的方法是用维基百科增强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.通过查看前面的令牌，您可以很容易地区分一元运算符和二进制运算符(我专门讨论的是负前缀和减法运算符)。如果没有前一个令牌，则前一个令牌是一个开括号，或者前面的令牌是一个运算符，那么您已经遇到了一个一元前缀运算符，否则您就遇到了二进制操作符。
Stack Overflow用户
发布于 2015-04-15 08:13:12
关于分流场算法的一个很好的讨论是parsing.htm，这里提出的算法使用了操作符栈的关键思想，但是有一些语法来知道下一步应该期望什么。它有两个主要函数E() (期望表达式)和P() (期望前缀操作符、变量、数字、括号和函数)。前缀运算符总是比二进制运算符绑定得更紧，所以您需要先处理这个问题。
如果我们说P代表某个前缀序列，而B是一个二进制运算符，那么任何表达式都是形式的。
P B P B P也就是说，你要么期待一个前缀序列或一个二进制运算符。语法在形式上是
E -> P (B P)*而P将是
P -> -P | variable | constant | etc.这转化为psudocode
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()
}您可以将其展开以处理其他一元运算符、函数、括号、后缀运算符。
https://stackoverflow.com/questions/29634992
复制相似问题
腾讯云开发者
