C--顺序栈.doc

一、利用栈类求进制转换：
顺序栈的应用：
1、用静态数组实现
#include <iostream>
using namespace std;
const int maxsize=10;
class stack
{
float data[maxsize];
int top;
public:
stack(void);
~stack(void);
bool empty(void);
bool full(void);
void push(float a);
float pop(void);
};
stack::stack()
{ top=0;
cout<<"stack initialized."<<endl;
}
stack::~stack()
{
cout<<"stack destroyed"<<endl;
}
bool stack::empty()
{
return top==0;
}
bool stack::full(void)
{return top==maxsize ;
}
void stack::push(float a)
{
if(full())
cout<<"Stack overflow!"<<endl;
else
{
data[top]=a;
top++;
}
}
float stack::pop(void)
{
if(top==0)
{
cout<<"An empty stack!"<<endl;
return 0;
}
top--;
return data[top];
}
int main( ) {
stack s;
int num,base,x;
cout<<"请输入一个十进制数\n";
cin>>num;
cout<<"请输入转换后的进制\n";
cin>>base;
while(num)
{
x=num%base;
s.push(x);
num=num/base;
}
cout<<"转换为"<<base<<"进制的数为:\n";
while(!s.empty())
{x=s.pop();
cout<<x;}
cout<<endl;
return 0;
}

2、用动态数组实现
/*_############################################################################
_## 动态数组实现的堆栈
_## Author: qishx
_## Time: 2010.4.8
_## sdupsl
_## Development condition: winxp +VC6.0
_##
_## dynamic_array.cpp 文件
_##########################################################################*/
#include <iostream>
using namespace std;

class Stack
{
int *data;
int size;
int top;
public:
Stack(int n=10 );
~Stack( );
bool isEmpty( );
bool isFull();
void push(int a);
int pop( );
};
Stack::Stack(int n)
{
size=n;
data=new int[size];
top=-1; //将栈指针top置为-1
cout<<"stack initialized."<<endl;
}

Stack::~Stack( )
{
delete [] data;
cout<<"stack destroyed."<<endl;
}

bool Stack::isEmpty( )
{
return top== -1?true:false;
}

bool Stack::isFull()
{
return top==size-1?true:false;
}

void Stack::push (int a)
{
if(isFull())
cout << "stack is full!"<< endl;
else
{
top ++;
data[top]=a;
}
}
/*改进的进栈操作
void Stack::push(int a)
{
if(top==size-1)
{
int *newdata=new int[size*2];
for(int i=0;i < = top;i ++)
newdata[i]=data[i];
delete [] data;
size=szie*2;
data=newdata;
}
data[++top]=a;
}
张铭《数据结构与算法》P50*/

int Stack::pop ( )
{
int num;
if (isEmpty())
{
cout << "stack is empty!"<< endl;
return -1;
}
else
{
num=data[top];
top--;
return num;
}
}

int main()
{
int num,base;
int x,n=0;
cout<<"请输入一个十进制数\n";
cin>>num;
cout<<"请输入转换后的进制\n";
cin>>base;
int temp1=num,temp2=base;
while(temp1)
{
n++;
temp1/=temp2;
}
Stack s(n);
while(num)
{
x=num%base;
s.push(x);
num=num/base;
}
cout<<"转换为"<<base<<"进制的数为:\n";
while(!s.isEmpty())
{
x=s.pop();
cout<<x;
}
cout<<endl;
return 0;
}

实训题目：简单计算器模拟：按输入的顺序计算，可求+-*/%运算。
结合模板应用：
//stack.h
#ifndef STACK_H
#define STACK_H

#include <iostream>
//#include <stdlib.h>
using namespace std;
const int MaxStackSize=50;

template <class T>
class Stack
{
private:
T stacklist[MaxStackSize];
int top;
public:
Stack();
void Push(const T& item); // 压栈
T Pop(); //出栈
void ClearStack();
T Peek() const;
int StackEmpty() const;
int StackFull() const;
};
//构造函数，将top置-1
template <class T>
Stack<T>::Stack():top(-1){}

//压栈
template <class T>
void Stack<T>::Push(const T& item)
{
if(StackFull()) //判断堆栈已满
{
cerr<<"stack overflow!"<<endl;
exit(1);
}
top++;
stacklist[top]=item;
}

//出栈
template <class T>
T Stack<T>::Pop()
{
T temp;
if(StackEmpty())
{
cerr<<"Attempt to pop an empty stack!"<<endl;
exit(1);
}
temp=stacklist[top];
top--;
return temp;
}

//清栈
template <class T>
void Stack<T>::ClearStack()
{
top=-1;
}

//返回栈顶元素
template <class T>
T Stack<T>::Peek() const
{
if(top==-1)
{
cerr<<"Attempt to peek at an empty stack!"<<endl;
exit(1);
}
return stacklist[top];
}

//判断栈空
template <class T>
int Stack<T>::StackEmpty() const
{
return top==-1;
}

//判断栈满
template <class T>
int Stack<T>::StackFull() const
{
return top==MaxStackSize-1;
}
#endif

//Calculator.h
#ifndef CALCULATOR_H
#define CALCULATOR_H

#include "stack.h"
#include <cmath>

template <class T>
class Calculator
{
private:
Stack<T> S; //存放操作数
void Enter(T num); //在栈中存放数据值

bool GetTwoOperands(T& opnd1,T& opnd2);//从栈中取得操作数并赋给形参
void Compute(char op); //运算求值
public:
Calculator(){}
void Run(void); //计算表达式的值
void Clear(void);//清空计算器
};

template <class T>
void Calculator<T>::Enter(T num)
{S.Push(num);}

//从栈中取得操作数并赋给形参
// 若操作数不够，则打印出错信息，并返回false
template <class T>
bool Calculator<T>::GetTwoOperands(T & opnd1,T& opnd2)
{
if(S.StackEmpty())
{
cerr<<"Missing operand1"<<endl;
return false;
}
opnd1=S.Pop(); // 取右操作数
if(S.StackEmpty())
{
cerr<<"Missing operand1"<<endl;
return false;
}
opnd2=S.Pop(); // 取左操作数
return true;
}

template <class T>
void Calculator<T>::Compute(char op)
{
bool result;
T oper1,oper2;
result=GetTwoOperands(oper1,oper2);
if(result==true)
switch(op)
{
case '+':
S.Push(oper1+oper2);
break;
case '-':
S.Push(oper1-oper2);
break;
case '*':
S.Push(oper1*oper2);
break;
case '/':
if(oper2==0)
{cerr<<"Divide by 0!"<<endl;
S.ClearStack();
}
else
S.Push(oper1/oper2);
break;
case '^':
S.Push(pow(oper1,oper2));
break;
}
else
S.ClearStack();//出错，清空计算器
}

template <class T>
void Calculator<T>::Run()
{
char c;
T operand;
while(cin>>c,c!='=')
{
switch(c)
{
case '+':
case '-':
case '*':
case '/':
case '^':
Compute(c);
break;
default:
cin.putback(c);
cin>>operand;
Enter(operand);
break;
}
}
if(!S.StackEmpty())
cout<<S.Peek()<<endl;
}

template <class T>
void Calculator<T>::Clear()
{
S.ClearStack();
}

#endif

//main.cpp
#include "Calculator.h"
int main()
{
Calculator<int> CALC;
CALC.Run();
return 0;
}