const int SM=100;
template<class Type> //顺序栈的类定义
class Stack
{
public:
Stack(int=100);//构造函数，初始化栈
~Stack()//析构函数，删除栈中的动态空间
{
delete []elements;
}
void Push(const Type &item);//向栈中插入元素
Type GetTop();//读取栈顶元素
Type Pop();//从栈中删除元素
void MakeEmpty()//清空栈
{ top=-1;}
int IsEmpty()const//判断栈是否为空
{
return top==-1;
}
int IsFull()const//判断是否已满
{
return top==MaxSize-1;
}
private:
Type *elements;//存放栈中元素的栈数组
int top;//栈顶指针
int MaxSize;//栈的最大可容纳元素个数
};
//---------------栈成员函数的实现---------------
template<class Type>Stack<Type>::Stack(int s):top(-1),MaxSize(s) //建立一个最大尺寸为s的空栈，若分配不成功则错误处理。
{
elements=new Type[MaxSize]; //创建栈空间
assert(elements!=0); //断言：动态存储成功分配与否
}
template<class Type>void Stack<Type>::Push(const Type &item)
{//若栈不满，则将元素item插入到该栈的的栈顶，否则出错处理
assert(!IsFull());
elements[++top]=item;
}
template<class Type>Type Stack<Type>::Pop()
{//如果栈不空则函数返回该栈顶元素的值然后栈顶指针退1
assert(!IsEmpty()); // 断言：判断栈空否，若断言成立则继续执行
return elements[top--]; //返回栈顶元素的值
}
template<class Type>Type Stack<Type>::GetTop()
{//若栈不空则返回该栈顶元素的值
assert(!IsEmpty()); //断言：判断栈空否，若断言成立则继续执行
return elements[top]; //返回栈顶元素的值
}
//----------------------------工具函数的定义------------------------------
//求运算符优先级
int Youxianji(char op)
{
switch (op)
{
case '+':
case '-': return 1;//定义加减运算的优先级为1
case '*':
case '/': return 2;//定义乘除运算的优先级为2
case '(':
case '[':
case '{':
case '=':
default: return 0;//定义在栈中的左括号和栈底字符的优先级为0
}
}
//将中缀表达式转换成后缀表达式
void Change(char *s1,char *s2)
{
Stack<char> R(SM);//定义用于暂存运算符的栈
R.Push('=');//给栈底放入‘='字符，它具有最低优先级0
int i,j;
i=0;//用于指示扫描s1串中字符的位置，初值为0
j=0;//用于指示s2串中待存字符的位置，初值为0
char ch=s1[i];
while(ch!='=')
{
if(ch==' ')
{
ch=s1[++i];//对于空格字符不做任何处理
}
else
if(ch=='(')
{//对于左括号，直接进栈
R.Push(ch);
ch=s1[++i];
}
else
if(ch==')')
{//对于右括号，使括号内的仍停留在栈中的运算符依次出栈并写入到s2中
while(R.GetTop()!='(')
{
s2[j++]=R.Pop();
}
R.Pop();//删除栈顶的左括号
ch=s1[++i];
}
else
if(ch =='[')
{//对于左括号，直接进栈
原文请找腾讯752018766辣,文-论'文.网http://www.751com.cn/ if(ch==']')
{//对于右括号，使括号内的仍停留在栈中的运算符依次出栈并写入到s2中
while(R.GetTop()!='[')
{
s2[j++]=R.Pop();
}
R.Pop();//删除栈顶的左括号
ch=s1[++i];
}
else
if(ch=='{')
{//对于左括号，直接进栈
R.Push(ch);
ch=s1[++i];
}
else
if(ch=='}')