[C++知识库]c语言实现中缀表达式转化为后缀表达式并求值

//这里可以我将输入的a-g赋了值
#include <stdlib.h>
#include <iostream>
using namespace std;

typedef char DataType;
 
//采用链式栈 
struct node{
    DataType element;  //数据元素 
	struct node *next; //指向下一个数据元素的指针 
};


typedef struct node *PtrToNode;
typedef PtrToNode Stack;
 
/*
   函数名：isEmpty 
   函数功能：判定栈是否为空 
   函数参数：栈头结点指针 
   返回值：若栈为空，则返回1，否则返回0
*/
int isEmpty(Stack s) 
{
    return  s->next ==NULL;
}

/*
   函数名：createStack 
   函数功能：创建一个空栈，实际上只需要初始化栈头结点 
   函数参数：无 
   返回值：栈头结点指针 
*/
Stack createStack(void)  
{
	Stack s ;
	s =new struct node;
	s->next = NULL;
	s->element =0;
	return s;
}

/*
   函数名：push 
   函数功能：向栈中压人一个数据元素值为x 
   函数参数：待压栈的数据元素，栈头结点指针 
   返回值：无
*/
void push(DataType  x,Stack s) 
{
	//表头作为栈顶
    PtrToNode temp ;
 	temp=new struct node;
 	temp->element = x;
 	temp->next = s->next;
 	s->next = temp;
}

/*
   函数名：pop 
   函数功能：弹出栈顶元素并返回元素值 
   函数参数：栈头结点指针 
   返回值：栈顶元素的值 
*/
DataType pop(Stack s) 
{
	PtrToNode temp;
	int t;
	if(isEmpty(s)==0)
  	{
  		temp = s->next;
  		t = temp->element;
  		s->next = temp->next;
  		free(temp);
 		 return t;
 	}
}

DataType top(Stack s) 
{
	if(isEmpty(s)==0)
  	{
    	return s->next->element ;
  	}
}
int youxian(char c)
{
	if(c==')')
	return 5;
	else if(c=='*')
	return 4;
	else if(c=='/')
	return 3;
	else if(c=='+')
	return 2;
	else if(c=='-')
	return 1;
	return 0;
}
float change(char s)

{
	if(s=='a')
	return 5.0;
	if(s=='b')
	return 4.0;
	if(s=='c')
	return 3;
	if(s=='d')
	return 2.0;
	if(s=='e')
	return 4.0;
	if(s=='f')
	return 1.0;
	if(s=='g')
	return 2.0;
	return s-'0';
}
char change1(int s)
{
	return s+'0';
}
/*
   函数名：inToPost
   函数功能：将中缀表达式转换为后缀表达式输出 
   函数参数：中缀表达式，放在字符数组中 
   返回值：无 
*/
int inToPost(char *expression)
{
   //在此处填写代码，完成中缀表达式转换为后缀表达式并输出
   /**********  Begin  **********/
   int i=0;
   float result=0,temp1=0,temp2=0;
   char a,temp=0;
   PtrToNode p1=createStack();
   PtrToNode p2=createStack();
   while(expression[i]!='\0')
   {
   	if(expression[i]>='a'&&expression[i]<'z'||(expression[i]>='1'&&expression[i]<'9'))
   	{
   		printf("%c",expression[i]);
   		push(expression[i],p1);
   		//printf("%d",change(expression[i]));
   	}
   	else
   	{
   		if(youxian(expression[i])==0)
   		{
   			push(expression[i],p2);
		   }
		else if(youxian(expression[i])==5)
		{
			 temp='!';
			 while(temp!='(')
			 {
			 	temp=pop(p2);
				 if(temp!='('){
					printf("%c",temp);
					switch(temp){
                       case '+': result=change(pop(p1))+change(pop(p1));; break;
                       case '-':temp1=change(pop(p1));temp2=change(pop(p1)); result=temp2-temp1;; break;
                       case '*': result=change(pop(p1))*change(pop(p1));; break;
                       case '/':temp1=change(pop(p1));temp2=change(pop(p1)); result=(float)temp2/(float)temp1;; break;
                   }
                   //printf("=%d=",result);
                   push(change1(result),p1);
				}
			 }
		}
		else if(youxian(expression[i])>youxian(top(p2))||isEmpty(p2)==1)
		{
			push(expression[i],p2);
		}
		else if(youxian(expression[i])<=youxian(top(p2)))
		{
			temp=pop(p2);
			printf("%c",temp);
			push(expression[i],p2);
			switch(temp){
                       case '+': result=change(pop(p1))+change(pop(p1));; break;
                       case '-':temp1=change(pop(p1));temp2=change(pop(p1)); result=temp2-temp1;; break;
                       case '*': result=change(pop(p1))*change(pop(p1));; break;
                       case '/':temp1=change(pop(p1));temp2=change(pop(p1)); result=(float)temp2/(float)temp1;; break;
                   }
                   //printf("=%d=",result);
                   push(change1(result),p1);
		}
	   }
   	
   	i++;
   }
   while(isEmpty(p2)==0)
   {
   	            temp=pop(p2);
				if(temp!='('){
					printf("%c",temp);
					
					switch(temp){
                       case '+': result=change(pop(p1))+change(pop(p1));; break;
                       case '-':temp1=change(pop(p1));temp2=change(pop(p1)); result=temp2-temp1;; break;
                       case '*': result=change(pop(p1))*change(pop(p1));; break;
                       case '/':temp1=change(pop(p1));temp2=change(pop(p1)); result=(float)temp2/(float)temp1;; break;
                   }
                   //printf("=%d=",result);
                   push(change1(result),p1);
				}
   }
   printf("\n结果为:%.2f",result);
   return result;
}
int main(void)
{
	char express[80];
	cin>>express ;
	printf("后缀表达式为："); 
	inToPost(express);
	//printf("\n结果为:%d",inToPost(express));
}