mmm2.cpp

用C++语言来实现

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>

/*=======================================================================
程序说明:用堆栈模拟表达式计算
1、只能实现加、减，乘、除和乘幂双目运算
2、受字符堆栈的限制，操作数只能是1位数的正整数，当运算结果超过2位数时不可预测
3、不作任何的操作数的有效性的检查
=======================================================================*/

char Operator[]=        {"+-*/()^#"};        //运算符  +  -  *  /  (  )  ^  #
int  OperatorPriority[]={1,1,2,2,0,0,3,-1};  //优先数　1  1  2  2  0  0  3  -1

typedef struct //定义栈结构体
{   
	char *base;
    int  top;
	int  stacksize;
}Stack;

void initStack(Stack *s)//初始化一个栈
{ 
	s->base=(char *)malloc(40*sizeof(char));
	if(!s->base) exit(1);
	s->top=0;
	s->stacksize=40;
}

int stackEmpty(Stack *s)//如果堆栈空，则函数返回1
{
	if(s->top==0) return 1;
	else return 0;
}

void clearStack(Stack *s)
{
	s->top=0;
}


int getTop(Stack *s,char *e) //取得栈顶元素的值
{ 
	if(stackEmpty(s)) return 0;
	else 
	{
		*e=*(s->base+s->top-1);
		return 1;
	}
}

void push(Stack *s,char e) 
{
	if(s->top == s->stacksize) //如果空间不够，补充空间
	{
		s->base=(char*)realloc(s->base,(s->stacksize+20*sizeof(char)));
		if(!s->base) exit(2);
		s->stacksize+=20;
	}
	*(s->base+s->top)=e; 
	s->top++;
}

int pop(Stack *s,char *e)
{
	if (!stackEmpty(s))	
	{
		*e=*(s->base+s->top-1); 
		--s->top;
		return 1;
	}
	else return 0;
}

int isOperator(char ch)//ch 是运算符，则函数返回1
{
	int i=0;
	while(Operator[i]!='\0')
	{
		if (Operator[i]==ch) return 1;
		else
		{   
			i++;
			continue;
		}
	}
	return 0;
}

int isHightPriority(char topOperatorInStack ,char currentOperator)
{
	//若栈顶运算符的优先数大于或等于当前运算符的优先数，则函数返回1	

	int i=0,j=0;
	int t_Priority=0,c_Priority=0;

	while(Operator[i]!='\0')
	{
		if (Operator[i]==topOperatorInStack) break;
		else
		{   
			i++;
			continue;
		}
	}
	t_Priority=OperatorPriority[i];

	while(Operator[j]!='\0')
	{
		if (Operator[j]==currentOperator) break;
		else
		{   
			j++;
			continue;
		}
	}
	c_Priority=OperatorPriority[j];

	if (t_Priority>=c_Priority) return 1;
	else return 0;
}

void transform(Stack *s,char exp[],char *suffix) 
{
	// 从合法的表达式字符串 exp 求得其相应的后缀式 suffix
	
    char *p = exp;
	char *q=suffix;
    char ch = *p;
	char *topInStack=(char *)malloc(sizeof(char));
	
	push(s,'#');
    while (!stackEmpty(s)) 
	{
		if (!isOperator(ch)) *(q++)=ch;// 若当前字符是操作数，直接发送给后缀式
        else 
		{
			switch (ch)//从"("到")"构成一个表达式。
			{
				// "("对它之前后的运算符起隔离作用,则若当前运算符为"("时进栈；
				case '(' : push(s, ch); break;

				// ")"可视为自相应左括弧开始的表达式的结束符，
				// 则从栈顶起，依次退出栈顶运算符发送给后缀式直至栈顶字符为"("止。
				case ')' : 		
				{
					pop(s, topInStack);
					while(*topInStack!='(')
					{ 
						*(q++)=*topInStack;
						pop(s,topInStack) ;
					}
                    break; 
				}
                default: 
				{   
					//若当前字符为运算符且优先数大于栈顶运算符，则进栈
				    //否则退出栈顶运算符发送给后缀式；

					while(getTop(s,topInStack) && isHightPriority(*topInStack,ch))
					{
						*(q++)=*topInStack;// 直接发送给后缀式
						pop(s,topInStack);
					}
					if ( ch!='#') push( s, ch); 
					break;
				} 
			} 
		}
        if ( ch!= '#') 
		{ 
			p++; 
			ch = *p; 
		}
	} 

	*q='\0';
}

int countResult(Stack *s,char *suffix)
{
	//后缀式运算规则,先找运算符，后找操作数
	char *p=suffix;
	char *ch=(char *)malloc(sizeof(char));
	int op1,op2,i,result=0;

	clearStack(s);

	while(*p!='#')
	{
		if (isOperator(*p))
		{
			pop(s,ch);
            op2=*ch-48; //字符转换成数字
			pop(s,ch);
			op1=*ch-48;

			switch(*p)
			{
				case '+': result=op1+op2;  break;
				case '-': result=op1-op2;  break;
				case '*': result=op1*op2;  break;
				case '/': result=op1/op2;  break;
				case '^': 
					{
						result=1;
						for(i=0;i<op2;i++) result=result*op1;
						break;
					}
			}
			*ch=result+48;
			push(s,*ch);
		}
		else
		{
			push(s,*p);
		}
		p++;
	}
	pop(s,ch);
	op2=*ch-48; //最终结果转换成数字，result=op2;

	return result;
}

void main()
{
	char str[]="2*3+(6-8/2)*2^3#";  //以#结束表达式
    char exp[20];

    Stack s;
	initStack(&s); 

	transform(&s,str,exp);
	printf("%s",&str);
	printf("=%d\n",countResult(&s,exp));

}