java - 实数(正数和负数)的中缀到后缀

Question

我编写了一个程序，允许将中缀表达式转换为后缀表达式，但它仅适用于一位数字[A-Z][a-z][0-9]。我怎样才能使实数(正数和负数)成为可能？

Example: (50 + 3.75) + 50 --> 50 3.75 + 50 +

doTrans() 允许从中缀转换为后缀

public String doTrans() {
        for (int j = 0; j < input.length(); j++) {
            char ch = input.charAt(j);
            theStack.displayStack("For " + ch + " ");
            switch (ch) {
            case '+':
            case '-':
                gotOper(ch, 1);
                break;
            case '*':
            case '/':
                gotOper(ch, 2);
                break;
            case '(':
                theStack.push(ch);
                break;
            case ')':
                gotParen(ch);
                break;
            default:
                output = output + ch;
                break;
            }
        }
        while (!theStack.isEmpty()) {
            theStack.displayStack("While ");
            output = output + theStack.pop();
        }
        theStack.displayStack("End ");
        return output;
    }

这一行的问题output = output + ch;。我找不到如何获取整个数字而不是仅一位数字的解决方案

Answer 1

你必须做Lexical analysis 。您必须将输入流转换为标记并对它们进行分类。目前您的程序已经这样做了，但它非常非常基本，您的 token 仅包含一位数字。尽管标记可以更复杂，但从大于 9 的简单整数文字、 float 文字、字符串文字、简单运算符等开始。

您现在可能拥有的是在后续调用中为您提供下一个 token 以进行分析、处理并进入下一个 token 的东西。像这样:

String input = "1 + 2";
int actPos = 0 ;

....

char getNextToken() {
    return input.charAt(actPos++);
}

您需要做的是重写getNextToken()，以便它为您提供一个“复杂” token (由多个数字/字符组成，因此是一个字符串)在下一步中进行分类。

String getNextToken() {
    String StringBuilder token = new StirngBuilde();

    // extract the next token from the input stream
    // using a state automata witch comes to a final
    // state when a token was recognized or an erroneous input

    return token.toString();
}

EIDT

您需要写finite state machine分析输入流并生成 token 。

给你一个非常简单的例子(假设你已经阅读了上面链接中的定义)，假设你有字母表{'0','1','2','3', '4','5','6','7','8','9'} 并且想要构建不带符号的整数标记。您将整数定义为 [0-9]+

您的状态机将需要至少三个状态 START 为开始状态，INTEGER 为最终接受状态，以及 ERROR 女巫表示输入有错误。

现在你需要一个转换函数和一个 state transition table ，这就是接受实际输入并根据实际状态产生下一个状态。

状态转换表可能看起来像这样(非常基本，在没有输入时无法处理)

              i n p u t
              +----------+----------+
              | [0-9]    | else     |
s  +----------+----------+----------+
t  | START    | INTEGER  | ERROR    |
a  +----------+----------+----------+
t  | INTEGER  | INTEGER  | ERROR    |
e  +----------+----------+----------+
   | ERROR    | ERROR    | ERROR    |
   +----------+----------+----------+

假设您有以下输入:27

• 开始时状态机的状态为START(实际状态)
• 您读取第一个字符 2 并将其与实际状态一起传递给转换函数
• 由于 2 是一个整数，因此您的函数会将您带到 INTEGER 状态，并且由于这不是 ERROR，因此您将其放入缓冲区中您可以在其中逐字符构建 token 。
• 现在，您读取下一个字符 7 并将其与实际状态 INTEGER 一起传递给转换函数。
• 7 也是一个整数，与 2 的情况相同。
• 现在 token 缓冲区的内容为 27，并且您的状态机仍然具有状态 INTEGER，这是接受状态，并且没有剩余输入。此时您可以返回 token 缓冲区的内容作为下一个 token 。

现在假设您有输入:2e7

你的状态机像上面一样进行第一个字符2和状态INTEGER，然后出现e女巫不符合规则上面定义的整数 ([0-9]+)。将带有实际状态 INTEGER 的 e 传递给转换函数会导致状态转换为 ERROR。此时您可以通知 e 的位置/索引处的输入有错误。

我的建议是您阅读更多有关词法分析以及如何编写有限状态机并实现它的内容。

话虽如此，您始终可以使用像 JLex 这样的工具它会为您生成此分析代码，但您仍然需要为其定义一些规则才能生成执行您希望它执行的操作的代码，女巫会引导您返回阅读有关词法分析的更多信息:)

祝你好运!