#include <iostream.h>
#include <stdio.h>
#include <stdlib.h>
#define maxsize 1000
#define DOUBLE_LEN 20
double stack[maxsize];
int top=-1;
void push(double value)  //進(jìn)棧
{
	if(top>=maxsize)
	{
		cout<<"Stack Full"<<endl;
        exit(-1);
	}
	stack[++top]=value;
}

double pop()           //棧頂元素出棧
{
	if(top<0)
	{
		cout<<"Stack Empty"<<endl;
        return -1;          //如果棧是空的返回-1
	}
	return stack[top--];
}

int priority(int op)          //返回運算符op所對應(yīng)的優(yōu)先級數(shù)值
{
	switch(op)
	{
	case '*':
    case '/':
		return 3;
    case '+':
    case '-':
		return 2;
    case '(':
		return 1;
    default:
		return 0;
	}
}

int isdigit(int num)           //如果是數(shù)字
{
	if((num>=48)&&(num<=57))
		return 1;
	else if(num=='.')
		return 1;
	return 0;
}

int check(char *str)          //返回值，1是正確，0是錯誤
{
	int count=0;
    char c_temp=0;
    while((c_temp=*(str++))!=0)
	{
		if(c_temp=='(')
			count++;
		else if(c_temp==')')
			count--;
	}
	return (count==0?1:0);
}

int isoperator(int op)
{
	switch (op)
	{
	case '*':
    case '/':
    case '+':
    case '-':
		return 1;
    default:
        return 0;
	}
}

char *back_expression(char *mid_expression)//將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式
{
	char c_temp=0;
    char *str_temp;
    int str_temp_pos=0;
    double stack_top_operator=0.0;/*operator on the top of stacl*/
    str_temp=(char*)malloc(maxsize);
    push((double)(';'));//把';'放入棧的底具有最底優(yōu)先級
    while((c_temp=*(mid_expression++))!=0)//讀如中綴表達(dá)式直到結(jié)束
	{
		if(c_temp=='(')//當(dāng)運算符是'('時
			push((double)c_temp);
        else if(isdigit(c_temp))//如果讀入的是數(shù)字或'.'，把它寫入 str_temp
		{
			str_temp[str_temp_pos++]=c_temp;
            while(((c_temp=*(mid_expression++))!=0)&&(isdigit(c_temp)))
			{
				str_temp[str_temp_pos++]=c_temp;
			}
			mid_expression--;
            str_temp[str_temp_pos++]=' ';
		}
		else if(c_temp==')')//如果讀入的是')'，運算應(yīng)該出棧直到'('
		{
			while((c_temp=(int)pop())!='(')//彈出棧中所有元素直到'('
				str_temp[str_temp_pos++]=c_temp;
		}
		else if(isoperator(c_temp))//如果字符是運算符，比較優(yōu)先級并決定入棧還是出棧
		{
			stack_top_operator=pop();
            while(priority((int)stack_top_operator)>=priority(c_temp))//'*','/'的優(yōu)先級數(shù)是3，'+','-'的優(yōu)先級數(shù)是2，否則是0
			{	str_temp[str_temp_pos++]=(int)stack_top_operator; 
                stack_top_operator=pop();
			}
			push(stack_top_operator);
            push((double)(c_temp));
		}
	}
	while((int)(stack_top_operator=pop())!=';')//彈出所有運算字符直到';'
    str_temp[str_temp_pos++]=stack_top_operator;
    str_temp[str_temp_pos]=0;
     return str_temp;
}

double cacl(char *back_expression)//將轉(zhuǎn)換得到的后綴表達(dá)式求值
{
	char c_temp=0;
    double temp1=0,temp2=0;
    char str_temp[DOUBLE_LEN]={0};
    int str_temp_pos=0;
    while((c_temp=*(back_expression++))!=0)
	{
		if((isdigit(c_temp))||(c_temp=='.'))
        str_temp[str_temp_pos++]=c_temp;
        else if(c_temp==' ')
		{
			str_temp[str_temp_pos]=0;
            push(atof(str_temp));
            str_temp_pos=0;
		}
		else if(c_temp=='+')
		{
			temp2=pop();
            temp1=pop();
            push(temp1+temp2);
		}
		else if(c_temp=='-')
		{
			temp2=pop();
            temp1=pop();
            push(temp1-temp2);
		}
		else if(c_temp=='*')
		{
			temp2=pop();
            temp1=pop();
            push(temp1*temp2);
		}
		else if(c_temp=='/')
		{ 
			temp2=pop();
            temp1=pop();
            push(temp1/temp2);
		}
	}
	return pop();
}

void main()
{
	char str[20];
	cout<<"請輸入中綴表達(dá)式："<<endl;
	cin>>str;
    if(check(str))
	{
		cout<<"轉(zhuǎn)換成的后綴表達(dá)式為："<<endl;
		cout<<back_expression(str)<<endl;
		cout<<"計算結(jié)果為："<<endl;
		cout<<cacl(back_expression(str))<<endl;
	}
	else
		cout<<"Wrong expression"<<endl;
}