整理了一下之前做过的一个实现混合四则运算的课设，对熟悉c语言中栈和队列的操作有帮助。

1.题目要求

输入一个中缀算术表达式,将其转换为后缀表达式,然后对后缀表达式进行求值。运算符包括+ - * / =,参与运算的为小于10的自然数。
功能要求及说明：
（1） 输入要求：可输入多组测试数据,每组数据对应一个算术表达式,当输入’=’
时表示输入结束。
（2） 输出要求：对每组数据输出2行,第1行为中缀表达式对应的后缀式,第2行为
后缀式求值的结果
（3） 输入样例：
9+(3-1)3+1/2=
1+2=
输出样例：
931-3+12/+
15
12+
3

算法提示：首先借助一个运算符栈将中缀表达式转换为后缀表达式，然后再借助一个运算符栈对后缀表达式进行求值。
附：中缀表达式变成等价的后缀表达式的算法：设立一个栈，存放运算符，从左到右扫描中缀表达式，若遇到操作数直接输出，若遇到运算符，则必须与栈顶算符比较，若当前读到的运算符级别高于栈顶运算符则进栈，否则退出栈顶运算符并输出；若遇到左括号，则进栈，继续读下一个字符；若遇到右括号，则一直做出栈并输出出栈运算符的操作，直到退到左括号为止。当表达式读完，栈变成空时，输出的结果即为后缀表达式。
后缀表达式的求值算法自行设计。

2.分析

2.1.目的

输入一个中缀算术表达式,将其转换为后缀表达式,然后对后缀表达式进行求值。运算符包括+ - * / =,参与运算的为小于10的自然数。

2.2.需求分析

1、输入要求
可输入多组测试数据,每组数据对应一个算术表达式,当输入’；’时表示输入结束。
2、输出要求
对每组数据输出2行,第1行为中缀表达式对应的后缀式,第2行为后缀式求值的结果。
3、样例
输入：9+(3-1)3+1/2;
输出：931-3+12/+
15.

2.3.概要设计

1、 编译环境：
vs2013。
2、 运行环境：
win平台。
3、目标功能：
输入一个中缀算术表达式,将其转换为后缀表达式,然后对后缀表达式进行求值。

2.4.详细设计

1、获取中缀表达式
使用cin函数输入字符串存于数组str。

2、转化为后缀表达式
依次获取str中存放的字符于字符变量c,接下来判断c为什么类型。
情况1：若为数字0~9，则压入后缀表达式队列post;
情况2：若为 ‘(’,则压入链栈S；
情况3：若为 ‘)‘和’;’ , 若链栈顶下一个节点不为 '('即 ‘±/’ 则压入队列post；
情况4：若为’±/’,其优先级小于链栈顶下一个节点x的优先级，则将x删除，并使x入队列post,然后使当前c入链栈S；

3、输出队列post，此即为后缀表达式

4、计算中缀表达式的值
依次判断str中存放的字符为什么情况。
情况1：若为数字0~9，则进整数栈n;
情况2：若为其他即字符则判断其优先级，与字符栈m中的栈顶元素的优先级进行比较（初始化字符栈顶存‘；’），大于则入字符栈m，小于则可以处理了（例如m中：; -> + -> * ->,当前若为-,优先级小于*,要先进行的运算），具体处理为：取出字符栈m中栈顶元素，若为+则抛出整数栈头2个数进行+操作再压入整数栈，若为-则抛出整数栈头1个数与当前数进行-操作再压入整数栈，若为则抛出整数栈头2个数进行*操作再压入整数栈，若为/则抛出整数栈头1个数进行/操作再压入整数栈，若为(则判断str里下一个字符，若为;则结束。最终字符栈m里为空，整数栈里只有栈头元素，此即表达式计算结果。

5、输出整数栈的栈头元素，此即表达式计算结果。

2.5.调试分析

编译器采用VS2013软件，在被调试函数加断点，之后按F5运行到断点出，再按F11进入函数，之后F10单步步过，在局部变量处加入相关变量，观察变量值的变化。

图1.转后缀时的链栈S存储情况

图2.计算表达式的值部分

2.6.测试结果

图3.输出调试结果

2.7.用户使用说明

用户使用键盘输入一个字符串即算数表达式，以回车键结束。软件会自动给出目标算数表达式的后缀表达式及计算结果。

2.8.课程设计总结

熟练掌握了栈和队列的相关操作，包括初始化栈，将元素压入栈，出栈，销毁栈，队列亦是。
进行中缀表达式转化为后缀时，采用两个结构，一个是队列post用来存放后缀表达式，一个是链栈S，用来按优先级存放运算符。进行计算表达式值时采用字符栈m和整数栈n分别存放对应运算符及数，结构清晰。
掌握了一些特殊情况的处理方法，如0不能做除数，栈为空时不能出栈，输入字符错误情况，印象深的是多位数的识别：处理时因一位一位判断，例如str里有31，判断时先识别到3（暂存在str[1]里），此时不能直接入栈，需要继续判断下一位是否还为数字，最后压入栈的是(*str[1]-48)*10+*str[2]-48。
设计过程中进一步加深了对多层循环的使用。

3. 源代码

#define SIZE 40
#include <string.h> 
#include <iostream> 
#include <stdlib.h> 
using namespace std;
#define MaxSize 32 

typedef char Qelemtype; 

typedef struct { 
	Qelemtype *base; //指向队列的存储空间； 
	int front; //指向队头元素； 
	int rear; //指向队尾元素的下一位置； 
}SqQueue; 

typedef struct LNode { 
	int data; 
	struct LNode *next; 
}Snode,*LinkStack; 


void DestroyLinStack(LinkStack &S) {//销毁链栈S。 
	LinkStack temp=S,p; 
	while(temp) 
	{ 
		p=temp; 
		temp=temp->next; 
		free(p); 
	} 
} 

void Push(LinkStack &S, char x) {//入栈。 
	LinkStack temp=(LinkStack )malloc(sizeof(Snode )); 
	temp->data=x; 
	temp->next=S->next; 
	S->next=temp; 
} 

void Pop(LinkStack &S, char &x) {//出栈。 
	LinkStack temp=S->next; 
	x=temp->data; 
	S->next=temp->next; 
	free(temp); 
} 

int GetTop(LinkStack &S) {//读栈顶元素. 
	int x; 
	if(S->next) 
		x=S->next->data; 
	else 
		cout<<"Stack Null "<<endl; 
	return x; 
} 

void Initstack(LinkStack &S) { 
	S=(LinkStack )malloc(sizeof(Snode )); 
	if(!S) 
	{ 
	cout<<"Alloctation Error"<<endl; 
	exit(1); 
	} 
	S->next=0; 
} 


int InitQueue(SqQueue &Q) {//队列的初始化； 
	Q.front=Q.rear=0; 
	Q.base=(Qelemtype *)malloc(MaxSize*sizeof(Qelemtype)); 
	if(!Q.base) 
		exit(1); 
	Q.base[Q.front]='\0'; 
	return 1; 
} 

int QueueLength(SqQueue Q) {//计算队列的长度； 
	return (Q.rear-Q.front+MaxSize)%MaxSize; 
} 

void EnQueue(SqQueue &Q, Qelemtype x) {//入队； 
	if(QueueLength(Q)==MaxSize) 
	{ 
		cout<<"EnQueue Error "<<endl; 
		return ; 
	} 
	Q.base[Q.rear++]=x; 
} 


void DispQueue(SqQueue Q) {//输出队列的所有元素； 
	int i=0,j=Q.front; 
	while(i<QueueLength(Q)) 
	{ 
		cout<<Q.base[j]; 
		if(Q.base[j]>=48&&Q.base[j]<=57&&Q.base[j-1]>=48&&Q.base[j-1]<=57)
			cout<<" ";
		j++; 
		i++; 
	} 
} 

void DestroyQueue(SqQueue &Q) { //队列的销毁； 
	delete []Q.base; 
	Q.base=0; 
	Q.front=Q.rear=0; 
	return ; 
} 


int StackEmpty(LinkStack S) {//判断栈是否为空. 
	return (S->next==0); 
} 

int Priority(char oper) { 
	switch(oper) 
	{ 
		case '(': 
			return 0; 
		case '+': 
		case '-': 
				return 1; 
		case '*': 
		case '/': 
			return 2; 
	} 
} 

void convertpostexp(char *str,SqQueue &post) { 
	char c,t; 
	int i=0,k=strlen(str); 
	LinkStack S; 
	Initstack(S); 
	Push(S,'('); 
	InitQueue(post); 
	while(i<k || !StackEmpty(S)) 
	{ 
		c=*str++; 
		switch(c) 
		{ 
			case '0': 
			case '1': 
			case '2': 
			case '3': 
			case '4': 
			case '5': 
			case '6': 
			case '7': 
			case '8': 
			case '9': 
				EnQueue(post, c); 
				break; 
			case '(': 
				Push(S,c); 
				break; 
			case ')': 
			case '=': 
				do{ 
					Pop(S,t); 
					if(t!='(') 
						EnQueue(post, t); 
				}while(t!='(' && !StackEmpty(S)); 
				break; 
			case '+': 
			case '-': 
			case '*': 
			case '/': 
				while(Priority(c)<=Priority(GetTop(S))) 
				{ 
					Pop(S,t); 
					EnQueue(post, t); 
				} 
				Push(S,c); 
				break; 
		} 
		i++; 
	} 
	DestroyLinStack(S); 
} 



struct node{//定义两个栈，存放字符
	char *base;
	char *top;        //头指针
	int size;
};
struct list{//整数栈
	float *base;
	float *top;
	int size;
};
node m;list n;             //定义两个对象

void Push2(list& S,float e){   //将整数放入栈中的算法
	*S.top++=e;
//cout<<e<<"已经被放入整数栈中"<<endl;
}

void Push(node& S,char e){     //将运算符放入栈中
	*S.top++=e;
//cout<<e<<"已经被放入字符栈中"<<endl;
}

float Pop2(list& S){
	if(S.base==S.top) cout<<"整数栈为空，不能输出";
	float x= *(--S.top);         //这里的*不代表乘法运算而是指针
//cout<<"计算值为"<<x<<endl;
	return x;
}

char Pop(node& S){
	if(S.base==S.top) cout<<"字符栈为空，不能输出";
	char x= *(--S.top);
//cout<<"出栈字符为"<<x<<endl;
	return x;
}

void InitStack(node& S){//初始化字符栈
	S.base=(char *)malloc(SIZE *sizeof(char));    //建立一个节点
	if(!S.base) {
   		cout<<"errer abc"<<endl;
        	exit(1);
	}
	S.top=S.base;
	S.size=20;
}

void InitStack2(list& S){
	S.base=(float *)malloc(SIZE *sizeof(float));     //建立一个节点
	if(!S.base) {
   		cout<<"errer efg"<<endl;
   		exit(1);
	}
	S.top=S.base;
	S.size=20;
}

int Prior(char c){                          
//这里的问题是解决比较优先级的时候如何处理运算符的值的大小，进而进入下一步的运算
//cout<<"要求栈内优先数的字符为"<<c<<endl;
	int r;
	switch(c)
	{
		case '=':r=0;break;
		case '(':r=1;break;
		case '*':
		case '/':r=5;break;
		case '+':
		case '-':r=3;break;
		case ')':r=8;break;
		default:cout<<"errer asdf"<<endl;
	}
	return r;
}

int Prior2(char c){
	int w;
//cout<<"要求栈内优先数的字符为"<<c<<endl;
	switch(c)
	{
		case '=':w=0;break;
		case '(':w=8;break;
		case '*':
		case '/':w=4;break;
		case '+':
		case '-':w=2;break;
		case ')':w=1;break;
		default:cout<<"errer sfd"<<endl;
	}
	return w;
}


float Compute(char* str){
	int i=0;
	float x;
	Push(m,'=');           //初始化字符栈，中只有一个元素';'，整数栈为空栈
	while(str[i]&&i<SIZE-1)   //处理中缀表达式循环
	{ 
  		x=0;
   		if(str[i]==' ') {i++;continue;}
   		while(str[i]>=48&&str[i]<=57) //这里的48到57 是十进制1到10的ASCII码值，这里主要是来处理多位数的输入操作
  	 	{
    		x=x*10+str[i]-48;     //从屏幕上获取的都是以字符的形式展现出来的，所以要ASCILL码值都要减去48 ，这样才能输入多位数
    		i++;
   		}
   		if(x!=0) Push2(n,x);     //如果x的值不等于 0那么就进整数栈
   		else
   		{
   			int a=Prior2(str[i]);   //处理栈外字符
  			int b=Prior(*(m.top-1)); //处理栈内字符，成员变量是字符栈中的栈顶元素
   			if(a>b)                  //栈外运算符优先级高于栈内运算符优先级
   			{
    			Push(m,str[i]);i++; //将其插入到字符栈中
			} 
   			else 
    		switch(Pop(m))       //优先级相反，括号里面的参数变量是字符栈内的首元素
   			{
    			case '+':x=Pop2(n)+Pop2(n); //从整数栈中抛出两个数值，进行以上的运算
     					Push2(n,x); break;
    			case '-':x=Pop2(n);
     					x=Pop2(n)-x;
     					Push2(n,x);break;
    			case '*':x=Pop2(n)*Pop2(n);
     					Push2(n,x);break;
    			case '/':x=Pop2(n);
     					if(x!=0.0)
     					{
						 x=Pop2(n)/x;Push2(n,x);
						}
     					else 
						{
							cout<<"零不能做除数"<<endl;i=SIZE-1;
						}
          				break;
    			case '(':i++;break;
    			case '=':i=SIZE-1;break;
    			default:cout<<"====输入有误===="<<endl;
   			} 
   		} 
	}
	x=Pop2(n);
	return x;
}

int main(){
	char str[32]; 
	char a[SIZE];
	InitStack(m);
	InitStack2(n);
	cout<<"请输入中缀表达式，以=结束:"; 
	cin>>str; 
	SqQueue post; 
	convertpostexp(str,post); 
	cout<<"转换成后缀表达式是:"<<endl; 
	DispQueue(post); 
	cout<<endl; 
	float z=Compute(str);
	DestroyQueue(post); 
	cout<<"结果为:"<<z<<endl;
}