#include <stdio.h>
#include <stdlib.h>
#define ERROR 0
#define OVERFLOW -2
#define STACK_INIT_SIZE 100
#define STACKINCREMENT   10

typedef struct Stack_c{
	char *base;
	char *top;
	int stacksize;
}Stack_c, *SqStack_c;

typedef struct Stack_d{
	double *base;
	double *top;
	int stacksize;
}Stack_d, *SqStack_d;

void InitStack_c (SqStack_c S) {
	S->base = (char *)malloc(STACK_INIT_SIZE * sizeof(char));
	if(!S->base) exit (OVERFLOW);
	S->top = S->base;
	S->stacksize = STACK_INIT_SIZE;
}

void InitStack_d (SqStack_d S) {
	S->base = (double *)malloc(STACK_INIT_SIZE * sizeof(double));
	if(!S->base) exit (OVERFLOW);
	S->top = S->base;
	S->stacksize = STACK_INIT_SIZE;
}

char GetTop_c (SqStack_c S) {
	char e;
	if (S->top == S->base) return ERROR;
	e = *(S->top-1);
	return e;
}

double GetTop_d (SqStack_d S) {
	double e;
	if (S->top == S->base) return ERROR;
	e = *(S->top-1);
	return e;
}

void Push_c (SqStack_c S, char e) {
	if (S->top - S->base >= S->stacksize) {
		S->base = (char *)realloc(S->base,(S->stacksize + STACKINCREMENT) * sizeof (char));
		if (!S->base)exit (OVERFLOW);
		S->top = S->base + S->stacksize;
		S->stacksize += STACKINCREMENT;
	}
	*S->top++=e;
}

void Push_d (SqStack_d S, double e) {
	if (S->top - S->base >= S->stacksize) {
		S->base = (double *)realloc(S->base,(S->stacksize + STACKINCREMENT) * sizeof (double));
		if (!S->base)exit (OVERFLOW);
		S->top = S->base + S->stacksize;
		S->stacksize += STACKINCREMENT;
	}
	*S->top++=e;
}

char Pop_c (SqStack_c S) {
	char e;
	if (S->top == S->base) return ERROR;
	e = *--S->top;
	return e;
}

double Pop_d (SqStack_d S) {
	double e;
	if (S->top == S->base) return ERROR;
	e = *--S->top;
	return e;
}

int Prio (char c) {
	switch (c) {
		case('#'): {return 0; break;}
		case('+'):
		case('-'): {return 1; break;}
		case('*'):
		case('/'): {return 2; break;}
		case('('): {return 3; break;}
		case(')'): {return 4; break;}
		default: return -1;
		}
	}

double Operate (double a, char y, double b) {
	switch(y) {
		case('+'): return (a+b);
		case('-'): return (a-b);
		case('*'): return (a*b);
		default: return (a/b);
		}
	}
  
int main()
{
	SqStack_c NU = (SqStack_c)malloc(sizeof(Stack_c));
	if(!NU) exit (OVERFLOW);
	SqStack_c OP = (SqStack_c)malloc(sizeof(Stack_c));
	if(!OP) exit (OVERFLOW);
	SqStack_d P =  (SqStack_d)malloc(sizeof(Stack_d));
	if(!P) exit (OVERFLOW);
	char num[50] = {'\0'}, c, s;
	double a, b;
	int i, t;
	printf("输入中缀表达式(以#结束)\n");
	scanf("%s", num);
	InitStack_c(OP); Push_c(OP,'#');
	InitStack_c(NU);
	InitStack_d(P);
	for(i = 0; num[i] != '\0'; i++) {
		c = num[i];
		if (Prio(c)<0) Push_c(NU,c);
		else if (Prio(c) == 3) Push_c(OP,c);
		else if (Prio(c) == 4) {
			while (GetTop_c(OP) != '(') Push_c(NU, Pop_c(OP));
			s = Pop_c(OP);
			}
		else {
			t = Prio(c)-Prio(GetTop_c(OP));
			if (t>0) Push_c(OP,c);
			else while(Prio(c)<=Prio(GetTop_c(OP))) Push_c(NU, Pop_c(OP));
			}
		}
	printf("转换成后缀表达式后为：\n");
	while (*NU->base!='#') {
	s = *NU->base;
	t = (double)(s - '0');
	printf("%c",s);
	if (s>=48&&s<=57) {Push_d(P,t); NU->base++;}
	else {
		b = Pop_d(P); a = Pop_d(P);
		Push_d(P, Operate(a, s, b));
		NU->base++;
		}
	}
	printf("\n表达式的结果为：\n");
	printf("%lf\n",Pop_d(P));
	return 0;
}