论坛 › 数据结构与算法 › 利用栈的特性实现的简单逆波兰运算（C++)

头狼 发表于 2016-4-9 19:29:52

利用栈的特性实现的简单逆波兰运算（C++)

/*"stacklist.h"——一个用C++类模块的方式编写的顺序存储式栈表的头文件，借用栈先进后出（FILO）的结构特性，实现小型逆波兰运算的功能*/
#include<iostream>
using namespace std;

const int maxsize=20;   //栈最大空间
template<class Selemtype>
class Stacklist
{public:
      Stacklist();
      void Push(Selemtype x);
      Selemtype Pop();
      int Empty();
private:
      Selemtype data;
      int top;
};
template<class Selemtype>
Stacklist<Selemtype>::Stacklist()    //栈的初始化，top=-1,栈顶位于栈底下边
{
      top=-1;
}
template<class Selemtype>
void Stacklist<Selemtype>::Push(Selemtype x)//压栈，将数据推入栈中
{
      if(maxsize-1==top)throw"Error";
      data[++top]=x;
}
template<class Selemtype>
Selemtype Stacklist<Selemtype>::Pop()    //弹栈，将栈顶数据弹出栈
{
      if(-1==top)throw"Error";
      return data;
}
template<class Selemtype>
int Stacklist<Selemtype>::Empty()    //判断是否为空栈
{
      if(-1==top)return 1;
      else return 0;
}

/*"stacklist.cpp"——一个借用栈将中缀表达式转换为后缀表达式，运用逆波兰实现表达式运算的源文件*/
#include<iostream>
#include"stacklist.h"
using namespace std;

Stacklist<double>data;   //创建存储double数据的栈表，用于暂时存储即将进行运算的值
Stacklist<char>symbol;   //创建存储char数据的栈表，用于暂时存储运算符号
int main()
{
      char c,s,str;
      int i=0;
      void calculator(char);   //传入运算符进行相应运算的函数
      cout<<"请输入中缀运算表达式，并以#作为结束字符："<<endl;
      cin>>c;
      while(1)
      {
                while(c>='0'&&c<='9')//由于输入都为char型，循环连续的数字输入，确保获取多位数值
                {
                        str=c;   //将一个一个输入的char型数字暂时存入一个char数组中
                        cin>>c;
                        if(c<'0'||c>'9')
                        {
                              str='\0';//在数值输入结束时，结尾存入‘\0'，代表当前数字字符串输入结束
                              data.Push(atof(str));   //asof函数用于将保存的数字字符转换为double型数值
                              i=0;   //char数组指标归零
                        }
                }
                if(')'==c)//当遇到')'时，由于括号内优先运算，则将先前入栈的运算符依次弹栈并同时从数据栈弹出两个数据用于计算（到弹出'('为止）
                {
                        s=symbol.Pop();
                        while('('!=s)
                        {
                              calculator(s);
                              s=symbol.Pop();
                        }
                }
                else if('*'==c||'/'==c||'('==c)   //由于'*','/','('的优先级较高，则先暂时压入栈中
                {
                        symbol.Push(c);
                }
                else if('+'==c||'-'==c)   //由于'+','-'优先级较低，则将栈中高级或等级的运算符弹栈以优先运算（直到遇上'('或栈空为止），最后还应将该运算符暂时压栈
                {
                        if(symbol.Empty())symbol.Push(c);   //如栈空则直接压栈
                        else
                        {
                              while(!symbol.Empty()&&'('!=s)
                              {
                                        s=symbol.Pop();
                              if('('==s)symbol.Push(s);    //当弹出的是'(',则重新压回栈中
                                        else calculator(s);
                              }
                              symbol.Push(c);
                        }
                }
                else if(c=='#')break;    //以'#'作为输入结束符
                else cout<<"输入字符格式出错"<<endl;
                cin>>c;
      }
      while(!symbol.Empty())   //最后将运算符栈中的所以运算符弹栈并进行运算
      {
                s=symbol.Pop();
                calculator(s);
      }
      cout<<"最后的运算结果为： "<<data.Pop()<<endl;   //从数据栈中弹出最终运算结果
      return 0;
}

void calculator(char c)   //进行相应的符号运算
{
      double d1,d2;
      d1=data.Pop();
      d2=data.Pop();
      switch(c)
      {
      case'+':
                data.Push(d2+d1);break;
      case'-':
                data.Push(d2-d1);break;
      case'*':
                data.Push(d2*d1);break;
      case'/':
                if(0==d1)cout<<"除数不能为0"<<endl;
                else data.Push(d2/d1);
                break;
      default:cout<<"运算符输出错误"<<endl;
      }
}

lxwd9394 发表于 2016-4-13 16:40:06

嗯嗯

326658hfh5yehhr 发表于 2016-4-13 22:25:58

学习学习路过

死幽亡灵 发表于 2016-5-16 00:50:20

XIE XIE L OU ZHU

zhouxcpython 发表于 2016-5-16 20:18:13

感谢分享

古老的问号 发表于 2016-5-22 15:13:11

看看

byf 发表于 2016-5-23 13:59:56

利用栈的特性实现的简单逆波兰运算

超超style 发表于 2016-5-25 13:17:55

vbbnm

鱼小鱼c 发表于 2016-5-26 14:46:21

{:5_92:}

查看完整版本: 利用栈的特性实现的简单逆波兰运算（C++)