-2

我正在为我在离散数学中的一项作业开发真值表生成器。我必须实现分流场算法，而这样做我完全迷失了。我的问题是实现调车码算法。首先，我将展示我查看过的资源，然后是我的问题，然后是我已经启动的代码。

我真正需要的..我知道它要求很多。但它是调车场算法的简化版本。当使用诸如 o1 o2 之类的符号时，我在维基百科示例中的部分内容中迷失了方向。我真正需要的是有人逐步解释如何应用它。我也不明白 RPN 符号是如何工作的。但我现在可以继续阅读。

这是一个示例输入：
A -> B
(C)
:. F

我应该生成一个显示的输入：
ABCA->BF
TTT--T---T
TFT--F---F
FTT--T---T
FFT--T---F
TTF-- T---F
TFF--F---F
FTF--T---F
FFF--T---F 

import java.util.Stack;
import java.util.ArrayList;

public class ShuttingYard{

private static final char THEREFORE = '>';
private static final char AND       = '&';
private static final char OR        = '|';


public static String inputToReversePolishNotation(String input)
{

    char[] tokens = input.toCharArray();
    ArrayList<String> output = new ArrayList<String>();
    Stack<String> oppStack = new Stack<String>();

    for(int i = 0; i < tokens.length; i++)
    {

    }

    return null;

}

public static boolean isLogicOperator(char input)
{

    switch(input)
    {
        case THEREFORE:
            return true;
        case AND:
            return true;
        case OR:
            return true;
        default:
            return false;
    }

}

}
4

1 回答 1

3

我相信你提到给你带来麻烦的具体一点是：

  • 如果令牌是运算符 o1，则：
    • 而在堆栈顶部有一个操作符标记 o2，并且
      • 要么 o1 是左结合的，并且它的优先级小于或等于 o2 的优先级，要么
      • o1 的优先级低于 o2，
    • 将 o2 从堆栈中弹出，进入输出队列；
  • 将 o1 压入堆栈。

我认为在这件作品上感到困惑是可以理解的。优先规则是 RPN 更易于解析的原因。在阅读它时，请记住，'o1' 是您正在阅读的运算符，而 'o2' 是堆栈顶部的运算符。

要处理它，您需要为运算符分配优先级值。例如，如果我们讨论算术，我可能会为优先值分配+= 1、*= 2 和= 3。^如果您正在读取的运算符的优先级低于或等于堆栈顶部的运算符，则将运算符从堆栈中弹出并将其传递给输出。这样做直到您在堆栈上找到一个优先级低于读取运算符的运算符，或者不再在堆栈的（新）顶部找到一个运算符。无论如何，您将把读取操作符压入堆栈。

就整个事情的一步一步而言，维基百科的文章非常好。请记住，定义的每条规则可能不适用于您的案例。从您定义的标记来看，您似乎不需要担心函数和括号，因此那里的算法可以简化为：

  • 虽然有要读取的令牌：
    • 读取令牌。
    • 如果令牌是数字，则将其添加到输出队列中。
    • 如果令牌是运算符 o1，则：
      • 当栈顶有一个操作符记号 o2，或者 o1 是左结合的并且它的优先级小于或等于 o2 的优先级，或者 o1 的优先级小于 o2 的优先级，
        • 将 o2 从堆栈中弹出，进入输出队列；
      • 将 o1 压入堆栈。
  • 当没有更多要读取的令牌时：
    • 虽然堆栈中仍有操作符标记：
      • 将操作员弹出到输出队列中。
  • 出口。

即使您确实需要括号和函数，它也可能有助于从更简单的问题开始，并在它起作用后对其进行增强。

于 2013-01-25T23:08:51.633 回答