来自「表达式的求值!!!!数据结构.实现功能!」· 代码 · 共 328 行

// 漏洞：01+2=3  误认为合法
//        (-2+3） 误认为非法 
//       1/0 默认为允许
  ////////////  以上漏洞已经修复 2007年5月22号
#include<iostream>
#include "计算.h"
#include "Windows.h"  //Sleep()函数
#define NUM 1
#define OPE 2 //判断字符的类型
#define RK 3
#define LK 4
#define END 5
#define OTHER -1

typedef char SElemType;

using namespace std;

 struct SqStack
{
	SElemType *base;
	SElemType *top;
	int stackSize;
		
};

int kind(const char c);
bool checkOrder( const char *q)  ;
bool canKuoHaoMatch(const char *c) ; //检查括号是否匹配
bool push(SqStack &S,SElemType e);
bool pop(SqStack &S,SElemType &e);
bool initSqStack(SqStack &S);
bool checkItNow(const SElemType *c);
char precede(const char a,const char b) ; //判断运算符a与b的优先级  
SElemType getTop(SqStack S);
float calExpress(const SElemType *c);


int main()
{
	char b[78];
    char c[80];
	while(true)
	{		
		cout<<"请输入表达式"<<endl;
		cin>>b;
		int j=0;
		if(b[0]=='-')  //若第一个字符为'-',则在它前面加上一个'0'
		{
			j=1;
			c[0]='0';
		}
		int i=0;
		while(b[i])		//将数组b处理后，存储到数组c
		{
			if(b[i]=='('&&b[i+1]=='-')  //若是这种情况 "(-    ",则数组c前三个字符为 "(0-   "
			{
				c[j++]=b[i++];
				c[j++]='0';
			}
			else
				c[j++]=b[i++];
		}

		c[j]='\0';
		if (!checkItNow(c))
		{
			Sleep(500);
			cout<<"你输入了非法表达式! "<<endl;
			Sleep(500);
			continue;
		}
		    
       	c[j]='#';
		c[j+1]='\0';
		
		cout<<b<<"=";
		Sleep(500);
		cout<<calExpress(c)<<endl;
		Sleep(500);
	}
	
	
	
	return 0;
}
bool initSqStack(SqStack &S)
{
	S.base =(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
	if(!S.base) return false;
	S.top=S.base;
	S.stackSize=STACK_INIT_SIZE;
	return true;
}
bool push(SqStack &S,SElemType e)
{
	if(S.top-S.base>=S.stackSize-1)
	{
		S.base =(SElemType *)realloc(S.base,(S.stackSize+STACKINCREMENT)*sizeof(SElemType));
		if(!S.base) return false;
		S.top =S.base +(S.stackSize -1);
		S.stackSize+=STACKINCREMENT;
	}
	*S.top=e;
	S.top+=1;
	
	return true;
}


bool pop(SqStack &S,SElemType &e)
{
	if (S.base==S.top) return false;
	e=*--S.top;
	return true;
}



SElemType getTop(SqStack S)
{
	SElemType e;
	if(S.base ==S.top) exit(1);
	e=*--S.top;
	return e ;
}


int kind(const char c)		//判定字符种类
{
	if(c>='0'&&c<='9')	//数字字符
		return NUM;
	if(c=='+'||c=='-'||c=='*'||c=='/')	//运算符号
		return OPE;
	if(c=='(')
		return LK;
	if(c==')')
		return RK;
	if(c=='\0')
		return END;
	return OTHER;  //其他非法字符
}
bool checkOrder(const char *q)  //检测表达式符号顺序是否正确
{
	if(kind(q[0])==OPE) return false;
	int t=0;	//判断是否正在扫描操作数
	while(*q!='\0')
	{
		int flag=kind(*(q+1));
		
		switch(kind(*q))
		{
		case NUM:
			t++;
			if(*q=='0'&&flag==NUM&&t==1) return false;  //非零数的第一位不能为零
			if(flag==OPE||flag==RK||flag==END||flag==NUM)	//数字后面只能是：运算符号，右括号，'\0',数字字符
			{
				q++;
				break;
			}
			else
				return false;
		case OPE:
			t=0;
			if(*q=='/'&&*(q+1)=='0')return false;  //分母不能为零
			if(flag==NUM||flag==LK)
			{
				q++;
				break;
			}
			else
				return false;
		case LK:
			t=0;
			if(flag==NUM||flag==LK)
			{
				q++;
				break;
			}
			else
				return false;
		case RK:
			t=0;
			if(flag==OPE||flag==END||flag==RK)
			{
				q++;
				break;
			}
			else
				return false;
		case OTHER:
			t=0;
			return false;
		}
	}
	return true;
}

bool canKuoHaoMatch(const SElemType *c)  //检查括号是否匹配
{
	SqStack kuo;
	SElemType a;
 	initSqStack(kuo);
	while(*c!='\0')
	{
		if('('==*c) push(kuo,*c);		//若为左括号则进栈
		if(')'==*c)			//若为右括号则出栈
		{
			if(kuo.base ==kuo.top ) return false;
			pop(kuo,a);
		}
		c++;
	}
	if(kuo.base ==kuo.top )		//遍历整个字符串后，若括号匹配，栈应该为空
		return true;
	else
		return false;
}
bool checkItNow(const SElemType *c)
{
	if(canKuoHaoMatch(c)&checkOrder(c))
		return true;
	else
		return false;
}

char precede(const char a,const char b)  //判断运算符a与b的优先级  
{                            //假设a，b都是合法字符,即表达式正确
	switch(a)
	{
	case '+':
		if(b=='*'||b=='/'||b=='(') 
			return '<';
		else
			return '>';
	case '-':
		if(b=='*'||b=='/'||b=='(') 
			return '<';
		else
			return '>';
	case '*':
		if('('==b)
			return '<';
		else
			return '>';
	case '/':
		if('('==b)
			return '<';
		else
			return '>';
	case '(':
		if (')'==b)
			return '=';
		else
			return '<';
	case ')':
		return '>';
	case '#':
		if(b=='#')
			return '=';
		else
			return '<';
	default:
		return ' ';
	}
}

float calExpress(const SElemType *c)	//运算表达式的值
{
	SqStack OPTR;
	calStack OPND;
	initSqStack(OPTR);
	push(OPTR,'#');
	initcalStack(OPND);
	while(*c!='#'||getTop(OPTR)!='#')
	{
		float temp=0;
		int i=0;   // i为数字的位数
		if(kind(*c)==NUM)
		{
			const SElemType *p;
			p =c;
			for(;kind(*p)==NUM;p++)	//当*p为数字时，计算出有几个数字字符连续个数
			{
				i++;
			}
			for(int j=i;j>=1;j--)
			{
				temp+=change(*c,j);
				c++;
			}	
			pushNum(OPND,temp);		//将操作数入栈
		}
		else
		{
			SElemType theta=getTop(OPTR);
			switch(precede(theta,*c))
			{
			case '<':
				push(OPTR,*c);
				c++;
				break;
			case '=':
				SElemType x;
				pop(OPTR,x);
				c++;
				break;
			case '>':
				float a,b;
				pop(OPTR,theta);
				popNum(OPND,b);
				popNum(OPND,a);
				pushNum(OPND,operate(a,theta ,b));
				break;
			}
		}
	}
	return getTopNum(OPND);
}