调车场功能

Question

我在 Java 程序中使用调车场算法 (https://en.wikipedia.org/wiki/Shunting-yard_algorithm) 来创建计算器。我快完成了，但我仍然需要实现功能。我有运行个问题：我希望计算器在将 x 和 y 放在一起时自动将变量相乘 - 示例：计算器将 xy 转换为 x*y。另外，我希望计算器将 (x)(y) 转换为 (x)*(y) 并将 x(y) 转换为 x*(y)。我使用以下代码完成了所有这些工作：

infix = infix.replaceAll("([a-zA-Z])([a-zA-Z])", "*");
infix = infix.replaceAll("([a-zA-Z])\(", "*(");
infix = infix.replaceAll("\)\(", ")*(");
infix = infix.replaceAll("\)([a-zA-Z])", ")*");

（在我的计算器中，变量名总是单个字符。）
这现在很好用，但是当我实现功能时，这当然不起作用。它会将 "sin(1)" 变成 "s*i*n*(1)"。如何让这段代码只对运算符而不是函数进行乘法转换？

Answer 1

预处理要解析的输入并不是实现您想要的内容的好方法。文本替换不知道解析算法知道什么，您也会丢失原始输入，这对于打印有用的错误消息很有用。

相反，您应该根据上下文来决定要做什么。将先前解析的标记的类型保留为输入开头的特殊类型。

如果前一个标记是一个值标记——一个数字、一个变量名或一个子表达式的右括号——而当前一个也是一个值标记，则发出一个额外的乘法运算符。

可以使用相同的逻辑来确定减号是一元否定还是二元减法：如果在值标记之后找到减号，则为减法，否则为否定。

您将 x(y) 转换为 x * (y) 的想法当然会与函数调用语法冲突。

Answer 2

我们可以将其分为两部分。括号表达式有一个规则，乘法有另一个规则。

而不是维基百科文章，这是为了解释目的而故意简化的，我会遵循一个更详细的例子，比如 Parsing Expressions by Recursive Descent 处理括号表达式。

这是我用于解析器的代码，它可以使用隐式乘法。我有多个字母的变量名，并使用 space 来分隔不同的变量，这样你就可以有 "2 pi r".

protected void expression() throws ParseException  {
    prefixSuffix();
    Token t = it.peekNext();
    while(t!=null) {
        if(t.isBinary()) {
            pushOp(t);
            it.consume();
            prefixSuffix();
        }
        else if(t.isImplicitMulRhs()) {
            pushOp(implicitMul);
            prefixSuffix();
        }
        else
            break;
        t=it.peekNext();
    }
    while(!sentinel.equals(ops.peek())) {
        popOp();
    }
}

这需要一些其他功能。

我使用了一个单独的分词步骤，将输入分解为离散的分词。 Tokens class 有很多方法，特别是 Token.isBinary() 测试运算符是否是像 +,=,*,/ 这样的二元运算符。另一种方法 Token.isImplicitMulRhs() 测试标记是否可以出现在隐式乘法的右侧，这适用于数字、变量名和左括号。

一个Iterator<Token>用于输入流。 it.peekNext() 查看下一个标记，it.consume() 移动到输入中的下一个标记。

pushOp(Token) 将一个令牌压入运算符堆栈，而 popOp 移除一个令牌并 . pushOp 具有处理不同运算符优先级的逻辑。如果优先级较低，则弹出运算符

protected void pushOp(Token op)
{
    while(compareOps(ops.peek(),op))
        popOp();
    ops.push(op); 
}

需要特别注意的是 implicitMul 一个与乘法具有相同优先级的人工标记，它被压入运算符堆栈。

prefixSuffix() 处理可以是数字和变量的表达式，带有可选的后缀运算符前缀。这将识别“2”、"x"、“-2”、"x++" 从输入中删除标记并将它们添加到适当的 output/operator 堆栈中。

我们可以把BNF中的这个套路想成

<expression> ::= 
          <prefixSuffix> ( <binaryOp> <prefixSuffix> )* // normal binary ops x+y
          | <prefixSuffix> ( <prefixSuffix> )*  // implicit multiplication x y

括号处理在 prefixSuffix() 中完成。如果检测到左括号，它将递归调用 expression()。为了检测匹配的右括号，一个特殊的哨兵标记被压入运算符堆栈。当在输入中遇到右括号时，主循环中断，运算符堆栈中的所有运算符弹出，直到遇到哨兵，控制权返回 prefixSuffix()。代码可能像

void prefixSuffix() {
    Token t = it.peekNext();
    if(t.equals('(')) {
         it.consume();  // advance the input
         operatorStack.push(sentinel);
         expression(); // parse until ')' encountered
         t = it.peekNext();
         if(t.equals(')')) {
             it.consume();  // advance the input
             return;
         } else throw Exception("Unmatched (");
     }
     // handle variable names, numbers etc 
}

Answer 3

另一种方法可能是使用标记，类似于解析器的工作方式。

第一阶段是将输入文本转换为标记列表，标记是表示找到的实体类型及其值的对象。例如，您可以有一个变量标记，它的值是变量的名称（'x'、'y' 等）、左括号或右括号的标记等。因为，我假设，你事先知道计算器可以使用的函数的名称，你也会有一个函数标记，它的值是函数名称。因此标记化阶段的输出区分变量和函数。

实现这个并不难，总是先尝试匹配函数名，所以 "sin" 将被识别为一个函数而不是三个变量。

现在第二阶段可以插入缺失的乘法运算符。现在这并不难，因为您知道只需将它们插入到：

{变量，RIGHT_PAREN}和{变量，LEFT_PAREN，函数}

但绝不会介于 FUNCTION 和 LEFT_PAREN 之间。

调车场功能

Shunting-yard functions

java

algorithm

evaluation

infix-notation

shunting-yard