#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<malloc.h>
#define MAX 100
typedef struct charnode                      //定义一个结构体类型 
{
    char charstack;                       //定义一个存放运算符的栈 
    struct charnode *next;                  //定义一个指向栈顶的指针变量 
}StackChar; 
typedef struct datanode 
{
	int data;                        //定义一个存放数据的栈  
	struct datanode *next;               //定义一个指向栈顶的指针变量 
}StackData; 
StackChar *operation;              //定义两个变量, 分别存储数字和运算符 
StackData *data;
char Operations[7]={'+','-','*','/','(',')','#'};   //括号和运算符 
StackChar *charInitstack();                        //运算符栈的初始化栈 
StackData *dataInitstack();                        //数据栈的初始化栈 
void  charPush(StackChar *top,char x );                      //运算符进栈 
void  dataPush(StackData *top,int x );                      //运算符进栈 
void  charPop(StackChar *top);                                //运算符出栈 
void  dataPop(StackData *top);                                //数据出栈 
char  charGetpop(StackChar *top);                   //取运算符栈顶
int  dataGetpop(StackData *top);                   //取数据栈顶  
char  Precede(char a, char b);         //运算符优先级判断
int judgechar(char test);          //判断字符类型  
int Operation(int a,char operationchar,int b);       //运算
int EvaluateExpression(char inputs[]);         
 
int main()
{

    int result;
	char inputs[MAX];
    printf("请输入算式表达式");
    gets(inputs);
    result=EvaluateExpression(inputs);      //调用表达式求值函数 
    printf("结果为%d\n",result);    
return 0;
}
StackChar *charInitstack()                        //运算符栈的初始化栈 
{
	StackChar *strack;
    strack=(StackChar *)malloc(sizeof(StackChar));
	strack->next=NULL;                       
    return (strack); 
}
StackData *dataInitstack()                        //数据栈的初始化栈 
{
	StackData *strack;
    strack=(StackData *)malloc(sizeof(StackData));
	strack->next=NULL;                        
    return (strack); 
}

void  charPush(StackChar *top,char x )                      //运算符进栈 
{
	StackChar *p;
	p=(StackChar *)malloc(sizeof(StackChar));
	p->charstack=x;
	p->next=top->next; 
	top->next=p;
}
void  dataPush(StackData *top,int x )                      //操作数进栈 
{
	StackData *p;
	p=(StackData *)malloc(sizeof(StackData));
	p->data=x;
	p->next=top->next; 
	top->next=p;
}
void charPop(StackChar *top)                                //运算符出栈 
{
	StackChar *p;
	if(top->next==NULL)
	   printf("栈已空，无法出栈");
	p=top->next;
	top->next=p->next;
	free(p);
 } 
 void dataPop(StackData *top)                                //数据出栈 
{
	StackData *p;
	if(top->next==NULL)
	   printf("栈已空，无法出栈");
	p=top->next;
	top->next=p->next;
	free(p);
 } 
char charGetpop(StackChar *top)                   //取运算符栈顶       
{ 
    char x;
	if(top->next==NULL)
	{
		printf("栈空，不能取栈顶元素");
		 return 0; 
	}
	else
	{
     x=top->next->charstack;
	 return(x); 
    } 
 }
int  dataGetpop(StackData *top)                   //取数据栈顶       
{ 
    int x;
	if(top->next==NULL)
	{
		printf("栈空，不能取栈顶元素");
		 return 0; 
	}
	else
	{
     x=top->next->data;
	 return(x); 
    } 
 }
/*比较两个运算符的优先级 
 *a，b中存放待比较的运算符 
 *'>'表示a>b 
 *'0'表示不可能出现的比较 
 */  
char Precede(char a, char b)
{  
    int i,j;  
    char pre[][7]={           
    /*运算符之间的优先级制作成一张表格*/  
        {'>','>','<','<','<','>','>'},  
        {'>','>','<','<','<','>','>'},  
        {'>','>','>','>','<','>','>'},  
        {'>','>','>','>','<','>','>'},  
        {'<','<','<','<','<','=',' '},  
        {'>','>','>','>',' ','>','>'},  
        {'<','<','<','<','<',' ','='}};  
    switch(a){  
        case '+': i=0; break;  
        case '-': i=1; break;  
        case '*': i=2; break;  
        case '/': i=3; break;  
        case '(': i=4; break;  
        case ')': i=5; break;  
        case '#': i=6; break;  
    }  
    switch(b){  
        case '+': j=0; break;  
        case '-': j=1; break;  
        case '*': j=2; break;  
        case '/': j=3; break;  
        case '(': j=4; break;  
        case ')': j=5; break;  
        case '#': j=6; break;  
    }  
    return pre[i][j];                  //返回优先级 
} 
/*进行实际的运算 
 *a，b中分别以整数的形式存放两个待运算的操作数 
 *operationchar中存放代表操作符的字符 
 *结果以整数的形式返回 
 */  
int Operation(int a,char operationchar,int b)       //运算
{
	switch(operationchar)
	{
		case '+':return a+b;
		        break;
		case '-':return a-b;
		         break;
		case '*':return a*b;
		         break;
	    case '/':return a/b;
	             break;
	    default: return 0;
	             break;
	}
}
int judgechar(char test)          //判断字符类型 
{
	int i;
	int find=1;
	for(i=0;i<7;i++)
	{
		if(test==Operations[i])
		    find=0;
	}
	return find;
}  
int EvaluateExpression(char inputs[])
{  
    int n;          //保存数据 
	char c;            //保存获取下一个的字符 
    char x,oper;      //x保存栈顶元素  ，oper保存运算符  
    int a,b,sum=0,i=0;           //临时变量，a、b 分别保存两个数据 
    data=dataInitstack(data);                  //初始化数据栈 
	operation=charInitstack(operation);       //初始化一个运算符栈     
    charPush(operation,'#');                 //插入一个'#'符     
    x=charGetpop(operation);               
    while(inputs[i]!='#'||x!='#')  
    {  
        if(judgechar(inputs[i]))                      //如果返回的值为1，说明该字符为整数 
         {   
            sum=inputs[i]-'0';
            while(judgechar(inputs[i++]))
            {
            	sum=sum*10+(inputs[i++]-'0');

			}
            printf("%d",sum);
            dataPush(data,sum);               //数据进栈 
			while(inputs[i++]==' ');        //跳过一个或多个空格 
		 }
		else                            //获取的字符是运算符
        {  
            x=charGetpop(operation);              //获取运算符栈的栈顶元素  
            switch(Precede(x, inputs[i]))             //比较两个运算符的优先级 
            {  
                case '<':            //栈顶元素优先级低                      
                    charPush(operation,inputs[i]);       //运算符进栈 
                    while(inputs[i]==' ');     //获取下一个字符 
                          i++;
                    break;  
                case '=':                  //脱括号并接受下一字符   
                    charPop(operation);         //出栈 
                    while(inputs[i]==' ');     //获取下一个字符
					    i++; 
                    break;  
                case '>':                 // 退栈并将运算结果入栈   
				        oper=charGetpop(operation);                                      
                        charPop(operation);    //运算符出栈 
                        a=dataGetpop(data);
                        dataPop(data);    //数据出栈
						b=dataGetpop(data); 
                        dataPop(data);         //数据出栈 
                        dataPush(data, Operation(a, oper, b));    //将两个数据运算后再进栈  
                        while(inputs[i++]==' ');     //获取下一个字符 
                        i++;
                        break;  
            }  
        }  
        x=charGetpop(operation);                    //获取运算符栈的栈顶元素 
    }  
    n=dataGetpop(data);             //获取数据栈的栈顶元素 
    printf("%d",n);
    return n;  
}