中缀表达式求值

问题描述

我想在C ++中评估（不转换）中缀表达式。如果你拥有算法，甚至实现这样的算法（可能不是C ++，任何语言...我会尝试重写它到C ++）分享。

给出表达式的值。 （2 + 2）* 3是12

对不起，我忘了我在谈论堆栈解决方案，因为我知道树解决方案，时间：（。

解决方案

如何得到这个表达式如果你得到

如果你有 34 + 12 * -1 +

的表达式， code>你可以像一个堆栈模拟程序集，如果你得到一个操作符弹出堆栈中的最后2个元素，并应用运算符：put 3 in stack，put 4 in stack，get op。 +所以弹出最后2个元素并使用运算符。现在你只有7在堆叠。现在阅读直到得到一个运算符，所以在堆栈中，你将有7 1 2后操作。 *在堆栈你有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  {
 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; 
默认值：
 break; 
} 
} 
} 
 
 return myStack.top（）; 
} 
 
 int main（int argc，char * argv []）
 {
 char * rpn =34 + 12 * -1 +; 
 
 int rez = GetResult（rpn）; 
 
 printf（％i，rez）; 
 
 return 0; 
} 
  

I would like to evaluate(not convert) infix expression in C++. If you posses algorithm or even implementation of such algorithm(may be not C++, any language... I will try to rewrite it to C++) share please.

Evaluation means give the value of expression. (2+2)*3 is 12

I am sorry, I forgot that I am talking about stack solution, cause I know the tree solution and It is not suitable this time : (.

解决方案

How do you got the expression? If you got it like (3 + 4) - (1 * 2) + 1 =

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

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

do a tree transversal of the tree like Left Root Right so it will be sth like this: 3 + 4 the result - the result of 1 * 2 the result + 1.

If you got the expression like 34+12*-1+ you can simulate assembly like do a stack and if you get to an operator pop the last 2 elements in the stack and apply the operator: put 3 in stack, put 4 in stack, get op. + so pop the last 2 elements and use the operator. Now you got only 7 in stack. Now read until get an operator so in the stack you will have 7 1 2 after op. * in stack you got 7 2 after op. - you get only 5 in stack add 1 in stack: Stack 5 1, use the last operator + and get the final result 6.

Ok, here is the code:

#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;
}

这篇关于中缀表达式求值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！