【数据结构】逆波兰表达式

前端之家收集整理的这篇文章主要介绍了【数据结构】逆波兰表达式前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

此篇文章中默认逆波兰表达式已经转换为后缀表达式

题意简述为;



解决问题的思想为:建立一个栈,把这些数据依次往栈里读,若读到数字入栈,若读到符号将栈顶元素保存到right中,pop掉当前元素,再将栈顶元素保存到left中将结果算出来在入栈,直到算完为止。

代码如下:


#include <iostream>
using namespace std;

#include "stack.hpp"

enum Type
{   
    ADD,SUB,MUL,DIV,OP_NUM,};  
struct Cell
{
    Type _type;
     int num;
};


//逆波兰表达式
long long   CountExp(Cell RPNExp[],int size)
{
    stack<Cell> s1;
    Cell sum;
    sum.num = 0;
     int i = 0;
     for(i=0;i<11;i++)
    {
          if(RPNExp[i]._type == OP_NUM)
         {
             s1.PushStack(RPNExp[i]);
         }
          else
         {
              int right = s1.GetTop().num ;
             s1.PopStack();
              int left = s1.GetTop().num ;
             s1.PopStack();
              switch(RPNExp[i]._type)
             {
              case ADD:
                  sum.num  = left + right;
                  break ;
              case SUB:
                  sum.num  = left - right;
                  break ;
              case MUL:
                  sum.num  = left * right;
                  break ;  
              case DIV :
                  sum.num  = left / right;
                  break ;
              default :
                  break;
             }
             s1.PushStack(sum);

         }
    }

     return sum.num ;
}


void Test6()
{
   Cell RPNExp[] = {
    OP_NUM,12,3,4,ADD,6,8,2,};

     long long num = CountExp(RPNExp,11);
    cout<<num<<endl;

    
}

int main()
{
   Test6();
   return 0;
}

猜你在找的数据结构相关文章