编写一个简单的公式解析器 [英] Writing a simple equation parser

问题描述

什么样的​​算法将被用于执行此操作（如，这是一个字符串，我想找到的答案）：

What sorts of algorithms would be used to do this (as in, this is a string, and I want to find the answer):

((5 + (3 + (7 * 2))) - (8 * 9)) / 72

说有人写在，我怎么能处理这么多的嵌套的括号？

Say someone wrote that in, how could I deal with so many nested parenthesis?

推荐答案

您可以使用调车场算法或逆波​​兰式，两者都使用栈来处理这个问题，维基说，更好的比我。

You can use Shunting yard algorithm or Reverse Polish Notation, both of them are using stacks to handle this, wiki said it better than me.

While there are tokens to be read:

    Read a token.
    If the token is a number, then add it to the output queue.
    If the token is a function token, then push it onto the stack.
    If the token is a function argument separator (e.g., a comma):

        Until the token at the top of the stack is a left parenthesis, pop operators off the stack onto the output queue. If no left parentheses are encountered, either the separator was misplaced or parentheses were mismatched.

    If the token is an operator, o1, then:

        while there is an operator token, o2, at the top of the stack, and

                either o1 is left-associative and its precedence is less than or equal to that of o2,
                or o1 is right-associative and its precedence is less than that of o2,

            pop o2 off the stack, onto the output queue;

        push o1 onto the stack.

    If the token is a left parenthesis, then push it onto the stack.
    If the token is a right parenthesis:

        Until the token at the top of the stack is a left parenthesis, pop operators off the stack onto the output queue.
        Pop the left parenthesis from the stack, but not onto the output queue.
        If the token at the top of the stack is a function token, pop it onto the output queue.
        If the stack runs out without finding a left parenthesis, then there are mismatched parentheses.

When there are no more tokens to read:

    While there are still operator tokens in the stack:

        If the operator token on the top of the stack is a parenthesis, then there are mismatched parentheses.
        Pop the operator onto the output queue.

Exit.

这篇关于编写一个简单的公式解析器的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！