4

我正在尝试获取一个表示完整代数表达式的字符串,例如 x = 15 * 6 / 3 这是一个字符串,并将其标记为各个组件。所以第一个是 x,然后是 =,然后是 15,然后是 *、6 和 /,最后是 3。

我遇到的问题实际上是解析字符串并查看单个字符。如果没有大量的 if 语句,我想不出办法来做到这一点。当然,必须有一种更好的方法来专门定义每个单独的案例并对其进行测试。

4

4 回答 4

3

对于每种类型的令牌,您需要弄清楚如何识别:

  • 当您开始读取特定令牌时
  • 如果您继续阅读相同的令牌,或者您已经开始使用不同的令牌

让我们举个例子: x=15*6/3. 让我们假设您不能依赖每个标记之间有空格的事实。在这种情况下,这很简单:当您到达一个空间时,您的新令牌就会启动。

您可以将字符类型分解为字母、数字和符号。我们将标记类型称为变量、运算符和数字。

字母表示变量令牌已启动。它会一直持续到你读到一封非信函。

符号表示操作员令牌的开始。我只看到单个符号,但您可以让符号组对应于不同的操作符标记。

数字表示数字标记的开始。(我们现在假设整数。) Number 标记一直持续到您读取非数字为止。

基本上,这就是一个简单的符号解析器的工作方式。现在,如果您添加负数(其中“-”符号可以有多种含义)、括号或函数名称(sin(x)如选择。

于 2013-06-17T22:11:50.213 回答
2

这是来自我早期的表达式评估器,它采用像您这样的中缀表达式并将其转换为后缀进行评估。有一些方法可以帮助解析器,但我认为它们非常自我记录。我的使用符号表来检查令牌。它还允许用户定义符号和嵌套分配以及您可能不需要/不想要的其他东西。但它显示了我如何在不使用正则表达式等细节的情况下处理您的问题,这将极大地简化这项任务。此外,显示的所有内容都是我自己的实现 - 堆栈和队列也是如此 -一切。因此,如果有任何东西看起来异常(与 Java imps 不同),那是因为它确实如此。

这部分代码很重要,不是回答您的直接问题,而是显示确定您正在处理的令牌类型的必要工作。就我而言,我有三种不同类型的运算符和两种不同类型的操作数。基于已知规则或我选择强制执行的规则(在适当时),很容易知道什么时候是数字(以数字开头)、变量/用户符号/数学函数(以字母开头)或数学运算符(是:/,*,-,+)。请注意,只需要看到第一个char就知道正确的提取规则。从您的示例中,如果您的所有情况都如此简单,则您只需要处理两种类型,运算符或操作数。尽管如此,同样的逻辑将适用。

protected Queue<Token> inToPostParse(String exp) {
    // local vars
    inputExp = exp;
    offset = 0;
    strLength = exp.length();
    String tempHolder = "";
    char c;

    // the program runs in a loop so make sure you're dealing
    // with an empty queue
    q1.reset();

    for (int i = offset; tempHolder != null && i < strLength; ++i) {
        c = exp.charAt(i); 

        // Spaces are useless so skip them
        if (c == ' ') { continue; }

        // If c is a letter
        if ((c >= 'A' && c <= 'Z')
                || (c >= 'a' && c <= 'z')) {

            // Here we know it must be a user symbol possibly undefined
            // at this point or an function like SIN, ABS, etc
            // We extract, based on obvious rules, the op
            tempHolder = extractPhrase(i); // Used to be append sequence
            if (ut.isTrigOp(tempHolder) || ut.isAdditionalOp(tempHolder)) {
                s1.push(new Operator(tempHolder, "Function"));
            } else {
                // If not some math function it is a user defined symbol
                q1.insert(new Token(tempHolder, "User"));
            }
            i += tempHolder.length() - 1;
            tempHolder = "";

        // if c begins with a number
        } else if (c >= '0' && c <= '9') {
            try {
                // Here we know that it must be a number
                // so we extract until we reach a non number
                tempHolder = extractNumber(i);
                q1.insert(new Token(tempHolder, "Number"));
                i += tempHolder.length() - 1;
                tempHolder = "";
            }
            catch (NumberFormatException nfe) {
                return null;
            }

        // if c is in the math symbol table
        } else if (ut.isMathOp(String.valueOf(c))) {
            String C = String.valueOf(c);
            try {
                // This is where the magic happens
                // Here we determine the "intersection" of the 
                // current C and the top of the stack
                // Based on the intersection we take action
                // i.e., in math do you want to * or + first?
                // Depending on the state you may have to move
                // some tokens to the queue before pushing onto the stack 
                takeParseAction(C, ut.findIntersection
                            (C, s1.showTop().getSymbol()));
            }
            catch (NullPointerException npe) {
                s1(C);
            }
        // it must be an invalid expression
        } else {
            return null;
        }
    }
    u2();
    s1.reset();
    return q1;
}

基本上我有一个堆栈(s1)和一个队列(q1)。所有变量或数字都进入队列。任何运算符 trig、math、parens 等都在堆栈上。如果要将当前标记放入堆栈,您必须检查状态(顶部)以确定要采取的解析操作(即,根据数学优先级做什么)。抱歉,这似乎是无用的信息。我想如果你正在解析一个数学表达式,那是因为你计划在某个时候评估它。恕我直言,后缀是最简单的,所以无论输入格式如何,我都将其更改为发布并使用一种方法进行评估。如果你的 O 不一样 - 做你喜欢的事。

编辑:实现
您可能最感兴趣的提取短语和数字方法如下:

protected String extractPhrase(int it) {
    String phrase = new String();
    char c;
    for ( ; it < inputExp.length(); ++it) {
        c = inputExp.charAt(it);
        if ((c >= 'A' && c <= 'Z') || (c >= 'a' && c <= 'z')
                        || (c >= '0' && c <= '9')) {
                    phrase += String.valueOf(c);
        } else {
            break;
        }
    }
    return phrase;
}

protected String extractNumber(int it) throws NumberFormatException {
    String number = new String();
    int decimals = 0;
    char c;
    for ( ; it < strLength; ++it) {
        c = inputExp.charAt(it);
        if (c >= '0' && c <= '9') {
            number += String.valueOf(c);
        } else if (c == '.') {
            ++decimals;
            if (decimals < 2) {
                number += ".";
            } else {
                throw new NumberFormatException();
            }               
        } else {
            break;
        }
    }
    return number;
}

记住——当他们输入这些方法时,我已经能够推断出它是什么类型。这使您可以避免看似无穷无尽的 while-if-else 链。

于 2013-06-17T22:19:09.653 回答
2
  1. 为每个可能的元素创建正则表达式:整数、变量、运算符、括号。
  2. 使用|正则表达式运算符将它们组合成一个带有捕获组的大正则表达式,以确定哪个匹配。
  3. 在循环中匹配剩余字符串的头部并将匹配的部分作为标记断开。令牌的类型取决于匹配的子表达式,如 2 中所述。

或者

使用词法分析器库,例如 antlr 或 javacc 中的

于 2013-06-17T23:12:09.923 回答
1

组件是否总是像您的问题一样由空格字符分隔?如果是这样,用于algebricExpression.split(" ")获取String[]组件。

如果不能假设这样的限制,一个可能的解决方案是迭代输入,以及switch当前索引的 Character.getType(),类似这样:

ArrayList<String> getExpressionComponents(String exp) {
    ArrayList<String> components = new ArrayList<String>();
    String current = "";
    int currentSequenceType = Character.UNASSIGNED;


    for (int i = 0 ; i < exp.length() ; i++) {
        if (currentSequenceType != Character.getType(exp.charAt(i))) {
            if (current.length() > 0) components.add(current);
            current = "";
            currentSequenceType = Character.getType(exp.charAt(i));
        }
        switch (Character.getType(exp.charAt(i))) {
            case Character.DECIMAL_DIGIT_NUMBER: 
            case Character.MATH_SYMBOL: 
            case Character.START_PUNCTUATION: 
            case Character.END_PUNCTUATION:
            case Character.LOWERCASE_LETTER:
            case Character.UPPERCASE_LETTER:
            // add other required types
                current = current.concat(new String(new char[] {exp.charAt(i)}));
                currentSequenceType = Character.getType(exp.charAt(i));
                break;
            default: 
                current = "";
                currentSequenceType = Character.UNASSIGNED;
                break;
        }
    }
    return components;
}

您可以轻松更改案例以满足其他要求,例如将非数字字符拆分为单独的组件等。

于 2013-06-17T23:02:15.217 回答