算术表达式求值.cpp

把算术表达式转换成后缀表达式然后求值。数据结构实验

#include<iostream>
#include<string>
#include<malloc.h>
#include<stdlib.h>
using namespace std;

typedef char selemtype;
#define stack_init_size 100  //存储空间初始分配量
#define stackincrement 10  //空间不足时每次追加10个

typedef struct{
	selemtype *base;  //在栈构造之前和销毁之后，base的值为null
	selemtype *top;   //栈顶指针
	int stacksize;  //当前容量
}sqstack;

typedef struct{
	int *base;
	int *top;
	int stacksize;
}intstack;

int initstack(sqstack &s){  //动态初始化栈
	s.base=(selemtype * )malloc(stack_init_size * sizeof(selemtype));
//	if(!s.base) exit (overflow);
	s.top=s.base;
	s.stacksize=stack_init_size;
    return 1;
}//initstack

selemtype gettop(sqstack s){
	return *(s.top-1);
}//gettop

int push(sqstack &s,selemtype e){  //插入元素e为新的栈点元素
	if(s.top-s.base>=s.stacksize){  //栈满，追加空间
		s.base=(selemtype*) realloc(s.base,
			(s.stacksize+stackincrement)*sizeof(selemtype));
//		if(!s.base) exit(overflow); //存储分配失败
	    s.top=s.base+s.stacksize;
	    s.stacksize+=stackincrement;
	}
    *s.top++=e;
	return 1;
}//push

selemtype pop(sqstack &s){
	if(s.top==s.base) return NULL;
	return *(--s.top);
}//pop

int stackempty(sqstack s){
	if(s.top==s.base) return 1;
	else return 0;
}//stackempty

int initstack(intstack &s){
	s.base=(int * )malloc(stack_init_size * sizeof(int));
	s.top=s.base;
	s.stacksize=stack_init_size;
    return 1;
}//initstack

int gettop(intstack s){
	return *(s.top-1);
}//gettop

int push(intstack &s,int e){
	if(s.top-s.base>=s.stacksize){
		s.base=(int*) realloc(s.base,(s.stacksize+stackincrement)*sizeof(int));
	    s.top=s.base+s.stacksize;
	    s.stacksize+=stackincrement;
	}
    *s.top++=e;
	return 1;
}//push

int pop(intstack&s){
	if(s.top==s.base) return NULL;
	return *(--s.top);
}//pop

int operation(int opr1, int opr2, char opt)//运算操作
{
	switch(opt)
	{
	case '+':
		return opr1 + opr2;
	case '-':
		return opr1 - opr2;
	case '*':
		return opr1 * opr2;
	case '/':
		return opr1 / opr2;
	default:
		return 0;
	}
}

/**************优先数表*****************/
int isp(char sign){
    switch(sign)
	{
	case'*':return 2;
	case'/':return 2;
	case'+':return 1;
	case'-':return 1;
	case'(':return 0;
	case'#':return -1;
	default:exit(1);
	}
}

int icp(char sign){
    switch(sign)
	{
	case'*':return 2;
	case'/':return 2;
	case'+':return 1;
	case'-':return 1;
	case'(':return 3;
	default:exit(1);
	}
}

int eval(char e[100]){//后缀表达式求值
	intstack OPND;
	initstack(OPND);
	int i=0;
	char c=e[i++];
	while(c!='#'){
		if(c>='0'&&c<='9'){
			int n=c-'0';
			while(e[i]!=' '){
				n=n*10+(e[i]-'0');
				i++;
			}
			push(OPND,n);
		}
		else{
			int t2=pop(OPND);
			int t1=pop(OPND);
			int t=operation(t1,t2,c);
			push(OPND,t);
		}
		c=e[i++];
		if(c==' ')
			c=e[i++];
	}
	return gettop(OPND);
}//eval

void postfix(char e1[100], char e2[100])//中缀表达式转后缀
{
	sqstack OPTR;
	initstack(OPTR);
	push(OPTR,'#');
	int i=0,j=0;
	char c=e1[i++];
	char x;
	while(c!=0)
	{
		if(c>='0'&&c<='9'){
			e2[j++]=c;
			if(e1[i]<'0'||e1[i]>'9')
				e2[j++]=' ';
		}
		else{
			if(c==')'){//连续出栈直到遇到“（”
				while(gettop(OPTR)!='(')
				{
					x=pop(OPTR);
					e2[j++]=x;
					e2[j++]=' ';
				}
				x=pop(OPTR);
			}//if
			else
			{
				while(isp(gettop(OPTR))>=icp(c))
				{
					x=pop(OPTR);
					e2[j++]=x;
					e2[j++]=' ';
				}
				push(OPTR,c);//当前运算符进栈
			}//else
			
		}//else
		c=e1[i++];
	}//while
	
	while(stackempty(OPTR)==0){
		e2[j++]=pop(OPTR);
	    e2[j++]=' ';
	}	
}//postfix
			
void main()
{
    char inexp[100];
	cout<<"请输入中缀表达式：";
	cin>>inexp;	
	char post[100];
	postfix(inexp,post);
	cout<<"转成后缀表达式为：";
	int i=0;
	while(post[i]!='#'){
		cout<<post[i];
		i++;
	} //while
	cout<<endl;
	cout<<"运算结果："<<eval(post)<<endl;
}