c++ - 中缀表达式评估

Question

<分区>

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入栈，得到op。 + 所以弹出最后 2 个元素并使用运算符。现在你只有 7 个堆栈。现在阅读直到得到一个运算符，所以在堆栈中你将在运算之后有 7 1 2。 * 在堆栈中，您在操作后得到 7 2。 - 你只得到 5 in stack add 1 in stack: Stack 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;
}