zhan1.cpp

简单的栈的使用,如入栈,出栈,及栈的调用

#include<iostream.h>
#include<math.h>
#include<stdlib.h>
#include<iomanip.h>
#include<string.h>
#include<fstream.h>
typedef char elemtype;
const int stackmaxsize=100;

struct stack
{//定义一个栈用于存放符号
	char stk[stackmaxsize];
	int top;
};

void change(char a[100]);  //转变为后缀表达式
int precedence(char op);  //判断所需符号的优先级数
char peek(stack &s);     //返回栈S的栈顶元素,但不能移动栈顶指针
void push(stack &s,const char &item);    //元素item进栈,即插入到栈顶
char pop(stack &s);         //删除栈顶元素并返回之
void initstack(stack &s);    //初始化栈

void main()
{
	cout<<"栈的使用 中缀表达式转换成后缀表达式  20053796 孔路明"<<endl;
	char a[100];
	cout<<"请输入一个以'@'字符结束的中缀算术表达式："<<endl;
	cin.getline(a,sizeof(a)); //从键盘上输入一行表示中缀算术表达式的字符串存入到字符数组a中
	change(a);
}

void change(char a[100])
{
	//a[]为原表达式
	char b[100]; //b[]为所求后缀表达式 
	int i=0,j=0;
	stack r;    //r为存放符号的栈
	initstack(r);  //栈初始化
	push(r,'@');   //栈底存入符号‘@’
	char ch=a[i];
	while(ch!='@')
	{
		if(ch==' ')  //对于空格字符不做任何处理，顺序读取下一个字符
			ch=a[++i];
		else if(ch=='(')
			{   //对于左括号，直接进栈、
				push(r,ch);
				ch=a[++i];
			}
			else if(ch==')')
				{   //对于右括号，使括号内的仍停留在栈中的运算符依次出栈并写入到s2中
					while(peek(r)!='(')
					{
						b[j++]=peek(r);
						b[j++]=' ';
						pop(r);
					}
					pop(r);  //删除栈顶的左括号
					ch=a[++i];
				}
				else if(ch=='+'||ch=='-'||ch=='*'||ch=='/')
					{
						b[j++]=' ';
						char w=peek(r);
						while(precedence(w)>=precedence(ch))
						{
							b[j++]=w;
							pop(r);
							w=peek(r);		
							b[j++]=' ';
						}
						push(r,ch);
						ch=a[++i];
					}
					else   
					{
						b[j++]=ch;
						ch=a[++i];
					}
				

	}
	//把暂存在栈中的运算符依次出栈并写入b串中
	ch=peek(r);
	while(ch!='@'){
		if(ch=='('){
			cerr<<"expression error!"<<endl;
			exit(1);
		}
		else {
			b[j++]=ch;
			b[j++]=' ';
			pop(r);
			ch=peek(r);
		}
	}
	//在后缀表达式的末尾放入表达式结束符和字符串结束符
	b[j++]='@';
	b[j++]='\0';
	cout<<"对应的后缀算术表达式为:"<<endl;
	cout<<b<<endl;
}

int precedence(char op)
{//返回运算符op所对应的优先级数值
	switch(op)
	{
		case '+':
		case '-':
			return 1; //加减运算的优先级为1
		case'*':
		case'/':
			return 2; //乘除运算的优先级为2
		case'(':
		case'@':
		default:
			return 0;  //在栈中其他字符的优先级为0
	}
}

char peek(stack &s)  
{//返回栈S的栈顶元素,但不能移动栈顶指针
	//若栈为空则终止程序运行
	if (s.top==-1)
	{
	   cout<<"Stack is empty!"<<endl;
	   exit(1);
	}
	return s.stk[s.top-1];
}

void push(stack &s,const char &item)
{//元素item进栈,即插入到栈顶
	//若栈已满则终止程序
	if(s.top ==stackmaxsize-1)
	{
	  cerr<<"stack overflow!"<<endl;
	  exit(1);
	}
	//将栈顶指针后移一个位置
	//将item的值赋值给新的栈顶位置
	s.stk[s.top]=item;
	s.top++;
}

char pop(stack &s)    
{//删除栈顶元素并返回之
	//若栈为空则终止程序
	if(s.top==-1)
	{ 
	    cout<<"Stack is empty!"<<endl;
		exit(1);
	}
	//暂存栈顶元素以便返回
	char temp=s.stk[s.top];
	//栈顶指针前移一个位置
	s.top--;
	//返回原栈顶元素的值
	return temp;
}

void initstack(stack &s)
{//初始化栈
	s.top=-1;
}