编写一个简单的方程解析器

Question

将使用哪种算法来实现此目的(例如,这是一个字符串,我想找到答案):

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

如果有人写到,我怎么能处理这么多嵌套的括号？

Answer 1

你可以使用Shunting yard算法或Reverse Polish Notation,它们都使用堆栈来处理这个问题,wiki说它比我好.

来自维基,

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.

Answer 2

解决这个问题的最简单方法是实现Shunting Yard 算法，将表达式从中缀表示法转换为后缀表示法。

使用大写字母 E 很容易评估后缀表达式。

Shunting Yard 算法可以用不到 30 行代码实现。您还需要标记输入（将字符串转换为操作数、运算符和标点符号的序列），但编写一个简单的状态机来实现这一点很简单。