#include <stdio.h>
#include <stdlib.h>
#include <math.h>


	struct stack
	{
		int top;
	    char element[20];
	};
	typedef struct stack Stack;


void Push(Stack *s, char element)
{

		s->top++;
		s->element[s->top] = element;
	
}


int icp(char c)                    //比較進棧優先級
{
	switch(c)
	{
	case'^':
		return(3);
	case'/':
	case'*':
		return(2);
	case'+':
	case'-':
		return(1);
	}
}


int isp(char c)                  //比較臨時棧頂優先級
{
	switch(c)
	{
	case'^':
		return(3);
	case'/':
	case'*':
		return(2);
	case'+':
	case'-':
		return(1);
	case('('):
		return(0);
	case(';'):
		return(-1);
	}
}

void mid_to_pos(char mid_exp[],struct stack * pos_exp)
{
    void Push(Stack * s, char element);
	int isp(char c);
	int icp(char c);
	char stack[20],c;                       //定義臨時棧
	int i,j;
	i=0;
	j=0;
	stack[0]=';';



	c=mid_exp[j];                                    //掃描表達式
	while(c!='\0')
	{
		if(c<='9'&&c>='0')
		{
			Push(pos_exp,c);
			if(mid_exp[j+1]>'9'||mid_exp[j+1]<'0')
			{
				Push(pos_exp,' ');
			}
		}
		else
			switch(c)
		{
			case('('):
				i=i+1;
				stack[i]=c;

				break;
			case('^'):
			case('*'):
			case('/'):
            case('+'):
	        case('-'):
				while(icp(c)<=isp(stack[i]))
				{
					Push(pos_exp,stack[i]);
					i=i-1;
				}
                i=i+1;
                stack[i]=c;
				break;
			case')':
				while(stack[i]!='(')
				{
					Push(pos_exp,stack[i]);
					i=i-1;
				}
				i=i-1;
				break;
			default:
				printf("確認輸入的是正確的中綴式!!!") ;               //表達式有誤
		}
		j=j+1;
		c=mid_exp[j];
	}
	while(i>=1)
	{
	Push(pos_exp,stack[i]);
	i=i-1;
	}
	Push(pos_exp,'\0');//**********************
}





void compvale(struct stack * pos_exp,int * p_x)
{
char c;
int j,i,k;
int x;
int sum_temp;            //把字符串轉為數值
int sum[20];              //存放已經轉換的數值
char temp[10];
++pos_exp->top;
j=0;
k=-1;
c=(pos_exp)->element[pos_exp->top];          
while(c!='\0')
{
	if(c<='9'&&c>='0')
	{
		temp[j]=c;
		++j;
		sum_temp=0;
		if(pos_exp->element[pos_exp->top+1]==' ')
		{
			for(i=0;i<j;++i)
			{
				sum_temp+=(temp[i]-48)*(int)pow(10,(j-1-i));         //把字符串轉為int
			}
			j=0;
			++k;
			sum[k]=sum_temp;
            ++pos_exp->top;
		}
	}
	else
		switch(c)
	{
		case('+'):
			x=sum[k--];
			sum[k]+=x;
			break;
		case('-'):
			x=sum[k--];
			sum[k]-=x;
			break;
		case('*'):
			x=sum[k--];
			sum[k]*=x;
			break;
		case('/'):
			x=sum[k--];
			sum[k]/=x;
			break;
		case('^'):
			x=sum[k--];
			sum[k]=(int)pow(sum[k],x);
			break;
		default:
			printf("計算失敗！！！");
	}
	c=pos_exp->element[++pos_exp->top];
}
*p_x=sum[0];
}



void main()
{
	
	struct stack pos_exp;
	pos_exp.top=-1;
    int i;

	char mid_exp[30];
	printf("input an expression:\n");
	scanf("%s",mid_exp);




    mid_to_pos(mid_exp,&pos_exp);
    
	for(i=0;i<=pos_exp.top;++i)
		printf("%c",pos_exp.element[i]);




    pos_exp.top=-1;
	int a;
	compvale(&pos_exp,&a);
	printf("%d",a);



}