c++ - 中缀表达式求值

Question

我想在 C++ 中评估（不转换）中缀表达式。如果您拥有算法甚至实现此类算法（可能不是 C++，任何语言......我会尝试将其重写为 C++）请分享。

评价手段赋予表达的价值。(2+2)*3 为 12

对不起，我忘了我在谈论堆栈解决方案，因为我知道树解决方案并且这次不合适:(。

Answer 1

你的表情是怎么来的？如果你得到它喜欢(3 + 4) - (1 * 2) + 1 =

                  +  
            /          \
           -            1
     /          \   
    +            *          
 /     \      /    \
3      4    1       2

http://cboard.cprogramming.com/cplusplus-programming/32682-inserting-infix-into-binary-tree.html

像这样对树进行树横断，Left Root Right它会像这样：3 + 4 结果 - 1 * 2 结果 + 1 的结果。

如果你得到了这样的表达式，34+12*-1+你可以像做一个堆栈一样模拟汇编，如果你得到一个运算符，弹出堆栈中的最后 2 个元素并应用运算符：将 3 放入堆栈，将 4 放入堆栈，获取操作。+ 所以弹出最后两个元素并使用运算符。现在你只有 7 个筹码。现在阅读直到得到一个运算符，所以在堆栈中你将在 op 之后有 7 1 2。* 在堆栈中，你在 op 之后得到 7 2。- 你在堆栈中只得到 5 在堆栈中添加 1：堆栈 5 1，使用最后一个运算符 + 并得到最终结果 6。

好的，代码如下：

#include <STACK>

int GetResult( char * rpn ) 
{
    std::stack<int> myStack;

    int nr1, nr2; int length = strlen(rpn);

    for (int i = 0; i < length; i++)
    {
        if (isdigit(rpn[i]))
        {
            myStack.push(rpn[i] - '0');
        }
        else
        {
            switch(rpn[i])
            {
                case '+':
                    nr1 = myStack.top();
                    myStack.pop();
                    nr2 = myStack.top();
                    myStack.pop();
                    myStack.push(nr2 + nr1);
                    break;

                case '-':
                    nr1 = myStack.top();
                    myStack.pop();
                    nr2 = myStack.top();
                    myStack.pop();
                    myStack.push(nr2 - nr1);
                    break;

                case '*':
                    nr1 = myStack.top();
                    myStack.pop();
                    nr2 = myStack.top();
                    myStack.pop();
                    myStack.push(nr2 * nr1);
                    break;

                case '/':
                    nr1 = myStack.top();
                    myStack.pop();
                    nr2 = myStack.top();
                    myStack.pop();
                    myStack.push(nr2 / nr1);
                    break;
                default:
                    break;
            }
        }
    }

    return myStack.top();
}

int main(int argc, char* argv[])
{
    char *rpn = "34+12*-1+";

    int rez = GetResult(rpn);

    printf("%i", rez);

    return 0;
}

Answer 2

到目前为止，最简单的方法是使用Dijkstra 的Shunting-yard 算法将中缀表达式转换为后缀表示法，并评估结果，这很简单。互联网上到处都有这样的代码示例（看看Rosetta 代码或LiteratePrograms）。

---

或者，如果您想学习，并且想进入解析的神奇世界和一点编译器理论，请编写递归下降解析器。很有趣。

---

哦，如果你想要更健壮的东西，你可以看看 Pratt 解析，这很棒。这是一篇关于它的好文章。