exp.cpp

处理了正确的算术表达式的转换为逆波兰式后进行计算

#include "stack.h"
#include <stdlib.h>
#include <iostream.h>
//********************************************************************
//----------------本示例只处理了正确的算术表达式的转换---------------*
//-----------可处理多位整型数的运算,如：10*(15-5)+30/3#-------------*
//********************************************************************
////////定义函数实现对两操作符优先级的比较//////////
char precede(char c1,char c2)
{
	if((c1=='+'||c1=='-')&&(c2=='+'||c2=='-'||c2==')'||c2=='#')) 
		return '>';
	if((c1=='*'||c1=='/'||c1==')')&&(c2=='+'||c2=='-'||c2=='*'||c2=='/'
		||c2==')'||c2=='#')) 
		return '>';
	if((c1=='('&&c2==')')||(c1=='#'&&c2=='#')) return '=';
	return '<';
}
//----定义转换函数(由原表达式得到逆波兰式--------------
//---exp传入原表达式存放位置，suffix为转换后存放的地址-------
void transform(char *suffix, char *exp) {
	Sqstack S;
	InitStack(S);  Push(S, '#');
	char *p = exp;  char ch = *p;
	int i=0;int c;
	while (!StackEmpty(S)) {//扫描表达式直到栈空
		if (!(ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch=='('||ch==')'||ch=='#'))
		   suffix[i++]=ch; 	//是数则输出
      	else {//是运算符时的处理
			suffix[i++]=' ';   //数与数之间用空格隔开
			GetTop(S,c);                                                                                                                                                                                                                                			switch (ch) {
				case '(' : 
					Push(S, ch); break;
				case ')' : 
					Pop(S, c);
					while (c!= '(' )
					{ suffix[i++]=c;  Pop(S, c); }       
					break; 
				default: 
					while(GetTop(S,c)&&(precede(c,ch)=='>'))	
						{ suffix[i++]=c;  Pop(S, c);}
					if ( ch!='#')  Push( S, ch); 
					break;  
			} 
		}
		if ( ch=='#' ) 
			{Pop(S, c);  suffix[i++]=ch; }
		else
			{ p++;  ch = *p;}//取下一个符号
	} 
	suffix[i]='\0';
	DestroyStack(S);
}
/////定义对后缀表达式计算的函数--------------------------------
int Evaluate(char *exp)
{
	Sqstack S;
	InitStack(S);  
	char *p = exp,ch=*p;
	int a,b,num;
	while(ch!='#'){//扫描后缀表达式一直到结束
		if(!(ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch=='('||ch==')'||ch=='#'||ch==' ')){
			num=ch-'0';
			ch=*(++p);
			while(!(ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch=='('||ch==')'||ch=='#'||ch==' ')){
				num=10*num+ch-'0';
				ch=*(++p);
			}

			Push(S,num);//将数字符号转换为数值压入栈
		}
		 
		else if(ch!=' '){//弹出两个数运算
			Pop(S,b);Pop(S,a);
			switch(ch)
			{
				case '+':Push(S,a+b);break;
				case '-':Push(S,a-b);break;
				case '*':Push(S,a*b);break;
				case '/':Push(S,a/b);break;
			}
		}
		p++;ch=*p;
	}
	Pop(S,a);//弹出计算结果并返回
	DestroyStack(S);
	return a;
	
}
/////////////主函数的定义------------------------
void main()
{
	char expression[80],result[80];
	cout<<"input exp:"<<endl;
	cin>>expression;
	transform(result,expression);
	cout<<result<<endl;
	cout<<Evaluate(result);
}