1

我在 Java 程序中使用 Shunting-Yard 算法 ( 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])", "$1*$2");
infix = infix.replaceAll("([a-zA-Z])\\(", "$1*(");
infix = infix.replaceAll("\\)\\(", ")*(");
infix = infix.replaceAll("\\)([a-zA-Z])", ")*$1");

（在我的计算器中，变量名总是单个字符。）
现在这很好用，但是当我实现函数时，这当然行不通。它将“sin(1)”变成“s*i*n*(1)”。我怎样才能让这段代码只为运算符而不是函数进行乘法转换？

4

3 回答 3

3

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

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

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

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

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

于 2015-10-29T10:40:01.507 回答
0

我们可以把它分成两部分。括号表达式有一个规则，乘法有另一个规则。

而不是为了解释目的而故意简化的维基百科文章，我将遵循更详细的示例，例如通过递归下降解析表达式，它处理括号表达式。

这是我用于解析器的代码，可以使用隐式乘法。我有多个字母的变量名称，并使用空格来分隔不同的变量，这样您就可以拥有“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有许多方法，特别是Token.isBinary()测试运算符是否是二元运算符，如 +、=、*、/。另一种方法Token.isImplicitMulRhs()测试标记是否可以出现在隐式乘法的右侧，这对于数字、变量名和左括号都是正确的。

AnIterator<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++”从输入中删除标记，并将它们适当地添加到输出/运算符堆栈中。

我们可以将 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 
}
于 2015-10-29T15:56:10.013 回答
0

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

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

实现这一点并不难，只是总是先尝试匹配函数名称，因此“sin”将被识别为一个函数而不是三个变量。

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

{VAR, RIGHT_PAREN} 和 {VAR, LEFT_PAREN, FUNCTION}

但绝不在 FUNCTION 和 LEFT_PAREN 之间。

于 2016-09-15T09:52:54.073 回答