8

我已经在java中成功实现了一个调车场算法。算法本身很简单，但是我在使用标记器时遇到了问题。目前，该算法适用于我想要的一切，不包括一件事。如何区分减法（-）和负数（-）

例如 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) 以获得正确的价值

4

5 回答 5

9

听起来您正在做一个 lex-then-parse 样式的解析器，您需要在词法分析器中使用一个简单的状态机，以便为一元和二进制减号获取单独的标记。（在 PEG 解析器中，这不是您必须担心的事情。）

在 JavaCC 中，您将有一个DEFAULT状态，您将在其中将-字符视为UNARY_MINUS. 当您标记主表达式的结尾时（根据您提供的示例，可以是右括号或整数），然后您将切换到INFIX将-被视为INFIX_MINUS. 一旦遇到任何中缀运算符，您就会返回到该DEFAULT状态。

如果您自己滚动，它可能会比这更简单一些。看看这个Python 代码，寻找一种聪明的方法。基本上，当您遇到 a 时-，您只需检查前一个标记是否是中缀运算符。该示例使用字符串"-u"来表示一元减标记，这便于进行非正式标记化。最好我能说的是，Python 示例确实无法处理 a-跟随开放括号或出现在输入开头的情况。这些也应该被认为是一元的。

为了在调车场算法本身中正确处理一元减号，它需要具有比任何中缀运算符更高的优先级，并且需要标记为右关联。（确保您处理右关联性。您可能已将其排除在外，因为其余的运算符都是左关联的。）这在 Python 代码中很清楚（尽管我会使用某种结构而不是两个单独的映射） .

当需要计算时，您需要稍微不同地处理一元运算符，因为您只需从堆栈中弹出一个数字，而不是两个。根据您的实现的样子，只需浏览列表并将每次出现的地方替换为"-u"with可能会更容易[-1, "*"]。

如果您完全可以使用 Python，那么您应该能够在我链接到的示例中看到我正在谈论的所有内容。我发现代码比其他人提到的 C 版本更容易阅读。另外，如果你很好奇，我不久前写了一篇关于在 Ruby 中使用 shutting-yard 的文章，但我将一元运算符作为单独的非终结符处理，因此没有显示它们。

于 2011-03-09T02:54:25.020 回答
3

这个问题的答案可能会有所帮助。

特别是，其中一个答案引用了C 中处理一元减号的解决方案。

基本上，您必须根据二元运算符不能出现的位置上的减号的外观来识别一元减号，并为其制作不同的标记，因为它具有不同的优先级。

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

于 2011-03-09T01:10:24.357 回答
1

在你的词法分析器中，你可以实现这个伪逻辑：

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

您可以设置否定的优先级高于乘法和除法，但低于求幂。您还可以将其设置为右关联（就像'^'）。然后，您只需按照 Wikipedia 页面上的描述将优先级和关联性集成到算法中。

如果记号是一个运算符 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);
}

Austin Taylor 说得非常正确，您只需要为一元运算符弹出一个数字：

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

于 2012-10-03T20:29:57.190 回答
1

这不是在 Java 中，但这是我在搜索并没有找到任何明确答案后专门为解决此问题而编写的一个库。这可以满足您的所有需求，甚至更多：

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

它是一个运行修改后的分流场算法的 ruby​​ 库（以及用于检查它的测试平台），该算法还支持一元 ('-a') 和三元 ('a?b:c') 操作。它还执行 RPN、Prefix 和 AST（抽象语法树）——您的选择，并且可以评估表达式，包括产生可以处理任何变量评估的块（某种 lambda）的能力。只有 AST 做全套操作，包括处理短路操作的能力（例如'||'和'?:'等），但 RPN做支持一元。它还有一个灵活的优先级模型，包括 C 表达式或 Ruby 表达式（不一样）所做的优先级预设。测试台本身很有趣，因为它可以创建随机表达式，然后可以 eval() 并通过 libExpr 运行以比较结果。

它有相当多的文档/评论，因此将这些想法转换为 Java 或其他语言应该不会太难。

一元运算符的基本思想是您可以根据先前的标记识别它们。如果前一个标记是运算符或左括号，则“可能的一元”运算符（+ 和 -）只是一元的，并且只能用一个操作数推送。重要的是，您的 RPN 堆栈区分一元运算符和二元运算符，以便它知道在评估时要做什么。

于 2022-01-12T02:48:58.680 回答
0

我知道这是一个旧帖子，但可能有人会觉得它有用。我之前实现了这个算法，从使用 StreamTokenizer 类的 toknizer 开始，它工作正常。在 Java 的 StreamTokenizer 中，有一些具有特定含义的字符。例如： ( 是一个运算符，sin 是一个词，...对于您的问题，有一个名为“streamToknizer.ordinaryChar(..)”的方法，它指定字符参数在此标记器中是“普通”。它删除该字符作为注释字符、单词组件、字符串分隔符、空格或数字字符具有的任何特殊意义。来源here

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

于 2013-11-10T20:22:38.987 回答