一个调车场算法存在的问题

Question

一个调车场算法存在的问题

javasubtractionshunting-yard

8

我已经成功地在Java中实现了一个Shunting Yard算法。算法本身很简单，但我在tokenizer方面遇到了麻烦。目前，该算法可以处理除一件事外的所有内容。如何区分减法(-)和负数(-)呢？

例如4-3是减法，但-4+3是负数。

现在我知道了什么时候应该是负数，什么时候应该是减号，但在算法中应该把它放在哪里呢？因为如果你像使用函数一样使用它，它不总是有效的。例如：

3 + 4 * 2 / -(1 - 5) ^ 2 ^ 3

当1-5变成-4时，它将在被平方和立方之前变成4。

就像 3 + 4 * 2 / cos(1 - 5) ^ 2 ^ 3，你会在平方和立方之前取余弦值。

但在真正的数学中，你不会这样做，因为你真正想说的是 3 + 4 * 2 / -((1 - 5) ^ 2 ^ 3)，以得到正确的值。

- The Dude

我添加了“java”标签，我认为这样可以让你的问题获得更多的关注。 - Trevor Boyle

5个回答

3

这个问题的答案可能会有所帮助。特别是其中一个回答提到了一个处理一元负数的C语言解决方案。

基本上，您需要根据减号出现的位置来识别一元负数，该位置不能是二进制运算符，然后为其创建不同的令牌，因为它具有不同的优先级。

Dijkstra的原始论文并没有太清楚地解释他是如何处理这个问题的，但是一元负号被列为单独的运算符。

- Don Roby

1

标准的Shunting Yard算法不支持它们，我正在尝试修改以支持它们。然而，Wolfram Alpha、德州仪器、Wolfram Mathematica、Microsoft Math等都支持它们，并且所有这些都使用Shunting Yard算法的某个版本。 - The Dude

3

虽然这不是用Java写的，但我在搜索并没有找到明确答案之后，写了一个库来专门解决这个问题。

这个库可以满足你的所有需求，甚至更多：

https://marginalhacks.com/Hacks/libExpr.rb/

它是一个ruby库（也是一个测试平台），使用修改后的逆波兰算法，支持一元运算符（'-a'）和三元运算符（'a?b:c'）。它还支持RPN、前缀和抽象语法树（AST），您可以根据需要进行选择，并且可以评估表达式，包括能够传入一个块（类似于lambda）来处理任何变量评估。只有AST才支持完整的操作集，包括处理短路运算符（如'||'和'？：'等），但RPN支持一元运算符。它还具有灵活的优先级模型，包括按C表达式或Ruby表达式预设优先级。测试平台本身非常有趣，因为它可以创建随机表达式，然后对其进行eval()，并通过libExpr运行以比较结果。

它有足够的文档/注释，所以将这些想法转换为Java或其他语言应该不会太难。

关于一元运算符的基本思想是，您可以根据上一个标记来识别它们。如果上一个标记是运算符或左括号，则“可能为一元”的运算符（+和-）就是一元运算符，只需推送一个操作数即可。重要的是，您的RPN堆栈区分一元运算符和二元运算符，以便在评估时知道该如何处理。

- David Ljung Madison Stellar

1

这里的答案提供了关于如何获得解决方案的信息。问题的年龄并不重要，因为通常还没有任何可用的解决方案。 - David Ljung Madison Stellar

（为了更明确，我写了这篇文章，特别是考虑到这个 StackOverflow 问题和我找不到普遍解决方案的事实） - David Ljung Madison Stellar

1

我已经明确表示，这是由我编写的，并且是为了解决这个确切的问题而编写的。顺便说一句，你提供的“易于找到”的链接似乎并没有帮助我真正找到任何东西，但我会相信你的。 - David Ljung Madison Stellar

1

谢谢。这个改进很大。已点赞。 - Scott Sauyet

很高兴我们能够找到方法让它成为更好的答案。 :) - David Ljung Madison Stellar

显示剩余2条评论

2

在你的词法分析器中，你可以实现以下伪代码逻辑：

if (symbol == '-') {
    if (previousToken is a number 
     OR previousToken is an identifier 
     OR previousToken is a function) {
        currentToken = SUBTRACT;
    } else {
        currentToken = NEGATION;
    }
}

您可以设置否定优先级高于乘除法，但低于指数运算。您也可以将其设置为右结合（就像'^'一样）。然后，您只需要按照维基百科页面上描述的方式将优先级和结合性集成到算法中即可。

如果令牌是运算符o1，则：当堆栈顶部有运算符令牌o2时，并且o1是左结合且其优先级小于或等于o2的优先级，或者o1的优先级小于o2的优先级，则弹出堆栈中的o2，推入输出队列; 将o1推入堆栈。

我最终实现了相应的代码。

} else if (nextToken instanceof Operator) {
    final Operator o1 = (Operator) nextToken;

    while (!stack.isEmpty() && stack.peek() instanceof Operator) {
        final Operator o2 = (Operator) stack.peek();

        if ((o1.associativity == Associativity.LEFT && o1.precedence <= o2.precedence)
         || (o1.associativity == Associativity.RIGHT && o1.precedence < o2.precedence)) {
            popStackTopToOutput();
        } else {
            break;
        }
    }

    stack.push(nextToken);
}

奥斯汀·泰勒是对的，你只需要弹出一个数字来进行一元运算符：

if (token is operator negate) {
    operand = pop;
    push operand * -1;
}

示例项目:

https://github.com/Digipom/Calculator-for-Android/

进一步阅读：

http://en.wikipedia.org/wiki/Shunting-yard_algorithm

http://sankuru.biz/blog/1-parsing-object-oriented-expressions-with-dijkstras-shunting-yard-algorithm

- Learn OpenGL ES

1

这看起来很不错，但是一元减运算符应该比任何其他运算符都具有更高的优先级。 - scrblnrd3

0

我知道这是一个旧帖子，但也许有人会觉得它有用。我之前实现过这个算法，首先使用StreamTokenizer类进行分词，它可以很好地工作。在Java的StreamTokenizer中，有一些具有特定含义的字符。例如：(是运算符，sin是一个单词，... 对于你的问题，有一个名为“streamToknizer.ordinaryChar(..)”的方法，它指定了字符参数在此标记生成器中是“普通”的。它会删除该字符作为注释字符、单词组件、字符串分隔符、空格或数字字符的任何特殊意义。源代码here

因此，您可以将“-”定义为普通字符，这意味着它不会被视为数字的符号。例如，如果您有表达式2-3，则会得到[2，-，3]，但如果您没有将其指定为普通字符，则会得到[2，-3]。

- Yasmin

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Austin Taylor · Accepted Answer

听起来你正在做一个词法分析器，然后再进行语法分析，为了得到单目和双目减号的不同标记，你需要在词法分析器中使用一个简单的状态机。 (在 PEG 分析器中，这不是你需要担心的问题。)

在 JavaCC 中，你将有一个 "DEFAULT" 状态，其中你将考虑 "-" 字符为 "UNARY_MINUS"。当你对主表达式的结尾进行标记化时（基于你给出的例子，这可以是闭合括号或整数），那么你将切换到 "INFIX" 状态，其中 "-" 将被视为 "INFIX_MINUS"。一旦遇到任何中缀运算符，你就会返回到 "DEFAULT" 状态。

如果你自己编写代码，那么可能会更简单一些。看看这个 Python 代码，它是一种聪明的方法。基本上，当你遇到一个 "-" 时，你只需要检查前一个标记是否为中缀运算符。该示例使用字符串 "-u" 来表示单目减号标记，这对于非正式标记化很方便。据我所知，Python 示例无法处理跟在开放括号后面或出现在输入开头的 "-" 情况。这些也应该被视为单目减号。

为了在Shunting-yard算法中正确处理一元减法，它需要比任何中缀运算符都具有更高的优先级，并且需要标记为右结合。（确保处理了右结合。由于您的其余运算符是左结合的，因此您可能已经遗漏了它。）这在Python代码中非常清楚（尽管我会使用某种结构而不是两个单独的映射）。

当评估时间到来时，您需要以略微不同的方式处理一元运算符，因为您只需要从堆栈中弹出一个数字，而不是两个数字。根据您的实现方式，最简单的方法可能是遍历列表并将每个"-u"的出现替换为[-1，"*"]。

如果您能够理解Python，您应该能够在我链接到的示例中看到我所说的一切。我发现这段代码比其他人提到的C版本要容易阅读一些。另外，如果您好奇，我之前写了一篇关于在Ruby中使用Shunting-yard的文章，但我将一元运算符作为单独的非终端处理，因此它们未显示。