数据结构课程设计----表达式求值

表达式求值问题         给定一个四则运算的中缀表达式，编程计算表达式的值。

基本要求：    

（1）在给定的表达式中要包含括号；    

（2）栈的操作要求自己完成，不允许调用类库中的方法；    

（3）对不同的操作编写相应的函数。

测试数据要求：         给定测表达式（字符串）中的数字字符要有包含两位以上的数字字符。

/***********************************************************************************************
***
第七题 算术表达式求值
[问题描述 ]
一个算术表达式是由操作数 (operand) 、运算符 (operator) 和界限符 (delimiter) 组成的。
假设操作数是正整数，
运算符只含加减乘除等四种运算符，界限符有左右括号和表达式起始、结束符 “#，
”
如：#（7+15）*（23-28/4 ）#。引入表达式起始、结束符是为了方便。
编程利用 “算符优先法 ”求算术表达式的值。
[基本要求 ]
（1） 从键盘读入一个合法的算术表达式，输出正确的结果。
（2） 显示输入序列和栈的变化过程。
************************************************************************************************
***/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <conio.h>
#include <ctype.h>
#define OK 1
#define ERROR 0
#define STACK_INIT_SIZE 100
//#define STACKINCREMENT 10
//========================================================
// 以下定义两种栈，分别存放运算符和数字
//========================================================
//******************* 运算符栈部分 *************************
struct SqStack //定义栈
{
	char * ; //栈底指针
	char *top; //栈顶指针
	int stacksize; //栈的长度
};
int InitStack (SqStack &s) //建立一个空栈 S
{
	if (!(s.  = (char *)malloc(50 * sizeof(char)))) 
		exit(0);
	s.top=s. ;
	s.stacksize=50;
	return OK;
}
char GetTop(SqStack s,char &e) //运算符取栈顶元素
{
	if (s.top==s. ) //栈为空的时候返回 ERROR
	{
		printf(\" 运算符栈为空 !\\n\");
		return ERROR;
	}
	else
		e=*(s.top-1); //栈不为空的时候用 e 做返回值，返回 S 的栈顶元素，并返回OK
	return OK;
}
int Push(SqStack &s,char e) // 运算符入栈
{
	if (s.top-s.  >= s.stacksize)
	{
		printf(\" 运算符栈满 !\\n\");
		s. =(char*)realloc (s. ,(s.stacksize+5)*sizeof(char) ); //栈满的时候，追加 5 个存储空间
		if(!s. ) exit (OVERFLOW);
		s.top=s. +s.stacksize;
		s.stacksize+=5;
	}
	*(s.top)++=e; //把 e 入栈
	return OK;
}
int Pop(SqStack &s,char &e) // 运算符出栈
{
	if (s.top==s. ) //栈为空栈的时候，返回 ERROR
	{
		printf(\" 运算符栈为空 !\\n\");
		return ERROR;
	} 
	else
	{
		e=*--s.top; //栈不为空的时候用 e 做返回值，删除 S 的栈顶元素，并返回 OK
		return OK;
	}
}
int StackTraverse(SqStack &s) // 运算符栈的遍历
{
	char *t;
	t=s.  ;
	if (s.top==s. )
	{
		printf(\" 运算符栈为空 !\\n\"); //栈为空栈的时候返回 ERROR
		return ERROR;
	}
	while(t!=s.top)
	{
		printf(\" %c\",*t); // 栈不为空的时候依次取出栈内元素
		t++;
	}
	return ERROR;
}
//********************** 数字栈部分 ***************************
struct SqStackn // 定义数栈
{
	int * ; //栈底指针
	int *top; //栈顶指针
	int stacksize; //栈的长度
};
int InitStackn (SqStackn &s) //建立一个空栈 S
{
	s. =(int*)malloc(50*sizeof(int));
	if(!s. )exit(OVERFLOW); //存储分配失败
	s.top=s. ;
	s.stacksize=50;
	return OK;
} 
int GetTopn(SqStackn s,int &e) // 数栈取栈顶元素
{
	if (s.top==s. )
	{
		printf(\" 运算数栈为空 !\\n\"); // 栈为空的时候返回 ERROR
		return ERROR;
	}
	else
		e=*(s.top-1); // 栈不为空的时候，用 e 作返回值，返回 S 的栈顶元素，并返回 OK
	return OK;
}
int Pushn(SqStackn &s,int e) // 数栈入栈
{
	if (s.top-s.  >=s.stacksize)
	{
	printf(\" 运算数栈满 !\\n\"); // 栈满的时候，追加 5 个存储空间
	s. =(int*)realloc (s. ,(s.stacksize+5)*sizeof(int) );
	if(!s. ) exit (OVERFLOW);
	s.top=s. +s.stacksize; // 插入元素 e 为新的栈顶元素
	s.stacksize+=5;
	}
	*(s.top)++=e; // 栈顶指针变化
	return OK;
}
int Popn(SqStackn &s,int &e) // 数栈出栈
{
	if (s.top==s. )
	{
	printf(\" 运算符栈为空 !\\n\"); // 栈为空栈的视时候，返回 ERROR
	return ERROR;
	}
	else
	{
	e=*--s.top; //栈不空的时候，则删除 S 的栈顶元素，用 e 返回其值，并返回 OK
	return OK;
	}
} 
int StackTraversen(SqStackn &s) // 数栈遍历
{
	int *t;
	t=s.  ;
	if (s.top==s. )
	{
		printf(\" 运算数栈为空 !\\n\"); // 栈为空栈的时候返回 ERROR
		return ERROR;
	}
	while(t!=s.top)
	{
		printf(\" %d\",*t); // 栈不为空的时候依次输出
		t++;
	}
	return ERROR;
}
//========================================================
// 以下定义函数
//========================================================
int Isoperator(char ch) // 判断是否为运算符，分别将运算符和数字进入不同的栈
{
	switch (ch)
	{
	case \'+\':
	case \'-\':
	case \'*\':
	case \'/\':
	case \'(\':
	case \')\':
	case \'#\':
	return 1;
	default:
	return 0;
	}
}
int Operate(int a, char op, int b) // 运算操作
{
	int result;
	switch(op)
	{ 
		case \'+\':
		result=a+b;
		break;
		case \'-\':
	result=a-b;
	break;
	case \'*\':
	result=a*b;
	break;
	case \'/\':
	result=a/b;
	break;
	}
	return result;
}
char Precede(char ch1, char ch2) // 运算符优先级的比较
{
	char p;
	switch(ch1)
	{
		case \'+\':
		case \'-\':
		if (ch2==\'+\'||ch2==\'-\'||ch2==\')\'||ch2==\'#\')
		p = \'>\'; //ch1 运算符的优先级小于 ch2 运算符
		else
		p = \'<\';
		break;
		case \'*\':
		case \'/\':
		if (ch2 == \'(\')
		p = \'<\';
		else
		p = \'>\';
		break;
		case \'(\':
		if (ch2 == \')\')
			p = \'=\';
		else if (ch2 == \'#\')
		{
			printf(\" 表达式错误 !运算符不匹配 !\\n\") ;
			exit(0);
		}
		else
			p = \'<\';
		break ;
		case \')\':
		if (ch2 == \'(\')
		{
			printf(\" 表达式错误 !运算符不匹配 !\\n\") ;
			exit(0);
		}
		else
			p = \'>\';
			break ;
		case \'#\':
		if (ch2 == \')\')
		{
			printf(\" 表达式错误 !运算符不匹配 !\\n\") ;
			exit(0);
		}
		else if (ch2 == \'#\')
		p = \'=\';
		else
		p=\'<\';
		break;
	}
	return p;
}
//========================================================
// 以下是求值过程
//========================================================
int Evaluate () //参考书 p53 算法 3.4
{
	int a, b, temp, answer;
	char ch,op,e;
	char *str;
	int j = 0;
	SqStackn OPND; //OPND 为运算数字栈
	SqStack OPTR; //OPTR 为运算符栈
	InitStack(OPTR);
	Push(OPTR,\'#\'); //,所以此栈底是 \'#\'，因为运算符栈以 \'#\'作为结束标志
	InitStackn(OPND);
	// printf(\"\\n\\n 按任意键开始求解 :\\n\\n\");
	// ch=getch(); 
	printf(\"\\n 请输入表达式并以 \'#\'结束:\\n\");
	str =(char*)malloc(50*sizeof(char));
	gets(str);
	ch=str[j]; //ch 是字符型的，而 e 是整型的整数
	j++;
	GetTop(OPTR,e); //e 为栈顶元素返回值
	while (ch!=\'#\' || e!=\'#\')
	{
	if (!Isoperator(ch)) //遇到数字 ,转换成十进制并计算
	{
	temp=ch-\'0\'; //将字符转换为十进制数
	ch=str[j];
	j++;
	while(!Isoperator(ch))
	{
	temp=temp*10 + ch-\'0\'; //将逐个读入运算数的各位转化为十进制数
	ch=str[j];
	j++;
	}
	Pushn(OPND,temp);
	}
	else if (Isoperator(ch)) //判断是否是运算符 ,不是运算符则进栈
	switch (Precede(e,ch))
	{
	case \'<\' : Push(OPTR,ch); // 栈顶元素优先权低
	ch = str[j++];
	printf(\"\\n\\n 运算符栈为： \\n\"); //输出栈，显示栈的变化
	StackTraverse(OPTR);
	printf(\"\\n 运算数栈为： \\n\");
	StackTraversen(OPND);
	break;
	case \'=\' : Pop(OPTR,op); // 脱括号并接收下一字符
	ch = str[j++] ;
	printf(\"\\n\\n 运算符栈为： \\n\");
	StackTraverse(OPTR);
	printf(\"\\n 数栈为： \\n\");
	StackTraversen(OPND);
	break; 
	case \'>\' : Pop(OPTR,op); //弹出最上面两个，并运算，把结果进栈
	Popn(OPND,b);
	Popn(OPND,a);
	Pushn(OPND,Operate(a,op,b));
	printf(\"\\n\\n 运算符栈为： \\n\");
	StackTraverse(OPTR);
	printf(\"\\n 数栈为： \\n\");
	StackTraversen(OPND);
	}
	else
	{
	printf(\" 您的输入有问题，请检查重新输入 !\");
	exit(0);
	}
	GetTop(OPTR,e); //取出运算符栈最上面元素是否是 \'#\'
	} //while
	GetTopn(OPND,answer); //已输出。数字栈最上面即是最终结果
	return answer;
}
//========================================================
// 执行部分
//========================================================
void ShowMenu()
{
	printf(\"\\n\\n\");
	printf(\" 表达式求值系统 \\n\");
}
void Quit();
void Manage()
{
	int answer;
	// ShowMenu();
	answer=Evaluate ();
	printf(\"\\n\\n 表达式结果是 : %d\\n\",answer);
		Quit();
}
void Quit()
{
	char ch;
	printf(\" 本次运算结束。 \\n\"); 
	printf(\" 继续本系统吗？ \\n\\n\");
	printf(\" 继续运算请按 Y/y \");
	printf(\"\\n 退出程序请按 N/n \");
	printf(\"\\n___________________________________________________________________\\n\");
	ch=getch();
	ch=toupper(ch); //将 ch 字符转换成大写字母
	if(ch == \'N\')
	{
	printf(\"\\n\\n 系统退出。 \\n\");
	exit(0);
		}
	Manage();
}
int main()
{
	ShowMenu();
	Manage();
	return 0;
}