基于栈的中缀表达式求值（含源码）-创新互联

相关数据结构：栈

创新互联服务项目包括将乐网站建设、将乐网站制作、将乐网页制作以及将乐网络营销策划等。多年来，我们专注于互联网行业，利用自身积累的技术优势、行业经验、深度合作伙伴关系等，向广大中小型企业、政府机构等提供互联网行业的解决方案，将乐网站推广取得了明显的社会效益与经济效益。目前，我们服务的客户以成都为中心已经辐射到将乐省份的部分城市，未来相信会继续扩大服务区域并继续获得客户的支持与信任！ 目录

• 实验内容
• 一、问题描述
• 二、输入与输出
• 代码实现

用栈解决表达式求值问题。(要求采用链式存储结构)

从键盘输入任意中缀表达式字符串，读字符串，利用栈结构实现表达式求值。

输入： 从键盘输入中缀表达式，如：32+5x（6-4）#，以#作为结束符
输出： 输出计算结果，如：42

#include#include#include#include#define OK 1


//定义操作数栈存储结构 
typedef struct caozs
{int data;
 	caozs *next;
}caozs,*caozsLink;

//定义操作符栈存储结构 
typedef struct caozf
{char data;
 	caozf *next;
}caozf,*caozfLink;


int initcaozf(caozfLink &s);
int initcaozs(caozsLink &s);
char* input_expr();
int just(char a);
int tran(char *a,int j);
caozsLink input_opnd(int m,caozsLink num);
caozfLink input_optr(char a,caozfLink sym);
int just_sym(char a,char b);
int calC(int b,int a,char c);
void cal(caozsLink &num ,caozfLink &sym);
float push(caozsLink num ,caozfLink sym,char *a);



//初始化操作符栈 
int initcaozf(caozfLink &s)
{s=(caozfLink)malloc(sizeof(caozfLink));
 	s->data=35;
 	s->next=NULL;
 	return OK;
}

//初始化操作数栈
int initcaozs(caozsLink &s) 
{s=(caozsLink)malloc(sizeof(caozs));
 	s->data=0;
 	s->next=NULL;
 	return OK;
}


//表达式输入
char* input_expr()
{char *a=(char*)malloc(sizeof(char)*100);
 	a[0]='1'; 
 	int i=-1;
 	do
	{i++;
  	a[i]=getchar();
 	}while(a[i]!='#');
 	return a;
}

//判断a是否为数字
int just(char a) 
{if(a>47&&a<58)
	return 1;
 	else 
	return 0; 
}

//字符转数字
int tran(char *a,int j) 
{int i=0, num1=0;
 	while(inum1+=(a[i]-48)*pow(10,j-i-1);
  	i++;
	}
 	return num1; 
}

//操作数入栈
caozsLink input_opnd(int m,caozsLink num)
{caozsLink s;
  	s=(caozsLink) malloc(sizeof(caozs));
  	s->data=m;
  	s->next=num;
  	num=s;
  	return num;
}

//操作符入栈 
caozfLink input_optr(char a,caozfLink sym)
{caozfLink s;
  	s=(caozfLink)malloc(sizeof(caozf));
  	s->data=a;
  	s->next=sym;
  	sym=s;
  	return sym;
}


int just_sym(char a,char b)
{int a1=0,b1=0;
 	if(a=='+'||a=='-')  
	 a1=1;
 	if(a=='*'||a=='/')  
	 a1=2;
 	if(a=='(') 
	 a1=3;
 	if(a==')') 
	 a1=-1;
 	if(a=='#') 
	 a1==0;
 	if(b=='#') 
	 b1==0;
 	if(b=='+'||b=='-')  
	 b1=1;
 	if(b=='*'||b=='/')  
	 b1=2;
 	if(b=='(') 
	 b1=-1;
 	if(b==')') 
	 b1=3;
 	if(a1==0 )  
	 return -2; 
 	if(a1>b1)  
	 return 1;
 	else if(a1==b1)
	{if(a1==-1)  
	  return 0;
  	  else  return -1;
 	}  
 	if(a1if(c=='+') 
	return b+a;
 	if(c=='-') 
	return b-a;
 	if(c=='*') 
	return b*a;
 	if(c=='/')
    return b/a;
}

//出栈计算
void cal(caozsLink &num ,caozfLink &sym)
{int a=num->data;
 	num=num->next;
 	int b=num->data;
 	int ss;
 	num=num;
 	ss=calC(b,a,sym->data);
 	num->data=ss;
 	sym=sym->next;
}


//入栈 
float push(caozsLink num ,caozfLink sym,char *a)
{int i=0;
 	char mm;
 	do{mm=a[i];
  		int j=0;
  		if(just(a[i])==1)
		{//a[i]是否为数字 
   			j++;
   			while(just(a[i+j])==1)//是否为多位数 ，j为多位数的位数
    		j++;
   			int m=tran(&a[i],j);//转换为数字 
   			num=input_opnd(m,num); //操作数入栈 
  			i+=j;
   		}
  		else if(just(a[i])==0)
		{switch (just_sym(a[i] ,sym->data))
			{ 		case 1: sym=input_optr(a[i],sym);break;
     		case 0:sym=sym->next; break;
     		case -1: i-=1;
      		cal(num,sym);  break;
     		case -2: while(a[i]!=sym->data)
        	cal(num,sym);
       		return num->data;
     		} 
   		i++;
  		}
 	}while(mm!='#');
}


int main()
{caozfLink sym;
 	caozsLink num;
 	initcaozf(sym);
 	initcaozs(num);
 	char *a;
 	a=input_expr();
 	int n=push(num,sym,a);
 	printf("%d",n);
	return 0;
}

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧