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

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

题意简述为;

解决问题的思想为：建立一个栈，把这些数据依次往栈里读，若读到数字入栈，若读到符号将栈顶元素保存到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;
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!