#include <stdio.h>
#include <malloc.h>
#include <iostream>
#include<math.h>
#include<string.h>

using namespace std;
typedef struct SNode{
union{
char c;
float fl;
}un;
float separate;//用来区分数字（1）和运算符（0）；

struct SNode *next;
}LNode,*Linklist;

typedef struct stack{
Linklist base;
Linklist top;
}Sqstack;
void Inital(Linklist &L)
{L=(Linklist)malloc(sizeof(LNode));
L->next=NULL;

}

void BuildList(Linklist &L)//建中缀链表
{
Inital(L);

Linklist p,k;
Inital(p);
Inital(k);

p=L;


{p->separate=0;
p->un.c='#';
cout<<L->un.c;
}

cout<<"请输入多项式的第一项，若为括号输入0，否则输入数字"<<endl;
float i;
cin>>i;
if(i==0)
{
k->separate=0;
k->un.c='(';
p->next=k;
p=p->next;
p->next=NULL;
}
else
{
k->separate=1;
k->un.fl=i;
p->next=k;
p=p->next;
p->next=NULL;

}
while(1)
{ Linklist n;
Inital(n);


cout<<"请输入多项式的下一项，若为运算符输入0，否则输入数字";
cin>>i;
if(i==0)
{
n->separate=0;
cin>>n->un.c;

p->next=n;
p=p->next;
p->next=NULL;
if(p->un.c=='#')break;
}
else
{
n->separate=1;
n->un.fl=i;
p->next=n;
p=p->next;
p->next=NULL;

}
}

system("pause");
}
void print(Linklist L)//输出链表
{
Linklist x;
Inital(x);
x=L;

while (x)
{
if(x->separate)
cout<<x->un.fl;
else
cout<<x->un.c;

x=x->next;
}

}

void BuildEmpty(Sqstack &S)
{
S.top=S.base=(Linklist)malloc(sizeof(LNode));

S.top=NULL;

}
void Push(Sqstack &S,Linklist t)

{


if(S.top==NULL)
{
S.top=t;

}
else
{t->next=S.top;
S.top=t;

}
}
void Pop(Sqstack &S, Linklist t)
{
t=S.top;
S.top=S.top->next;
free(t);

}
void GetTop(Sqstack s,Linklist t)
{
if(s.top)
if(s.top->separate)
{t->un.fl=s.top->un.fl;
cout<<t->un.fl;}

else { t->un.c=s.top->un.c;
cout<<t->un.c;}

}
char PreCedeJudge(char c1,char c2)//判断运算符 优先级
{
cout<<"调用函数PreCedeJudge";
system("pause");
switch(c1)
{
case'+':
if(c2=='*' || c2=='/' || c2=='(')
return '<';
else return '>';
break;
case'-':
if(c2=='*' || c2=='/' || c2=='(')
return '<';
else return '>';
break;
case'*':
if(c2=='(')
return '<';
else return '>';
break;
case'/':
if(c2=='(')
return '<';
else return '>';
break;
case'(':
if(c2==')')
return '=';
else return '<';
break;
case')':
return '>';
break;
case'#':
if(c2=='#' )
return '=';
else return '<';
break;
}


}
float Caculate(float a,char theta,float b)
{
float c;
cout<<"S输出结果"<<endl;
switch (theta)
{
case '+':
c=a+b;
cout<<c;
return c;
break;
case '-':
c=a-b;
cout<<c;
return c;
break;
case '*':
c=a*b;
cout<<c ;
return c;
break;
case '/':
c=a/b;
cout<<c;
return c;
break;
}
}
int Caculation_process(Linklist L,Sqstack optr,Sqstack opnd)//将链表用栈计算
{
//cout<<"调用函数Caculation_Process()"<<endl;;
Linklist h,x,y,th,z; int c;
Inital(h);
Inital(x);
Inital(y);
Inital(th);
Inital(z);

Push(optr,L);
cout<<"调用函数Caculation_Process()2"<<endl;;

L=L->next;
while(L!=NULL)

{ cout<<"调用函数Caculation_Process()3"<<endl;;
if(L->separate)
{
Push(opnd,L);cout<<"调用函数Caculation_Process() if(L->separate）的时候调用"<<endl;;
/*Linklist t;
t=(Linklist)malloc(sizeof(LNode));
if(opnd.top==NULL)
{
opnd.top=t;
opnd.top->next=NULL;
}
else
{t->next=opnd.top;
opnd.top=t;
opnd.top->next=NULL;
}*/
L=L->next;
}

if(L->separate==0)

{
GetTop(optr,h);
cout<<"调用函数Caculation_Process() if(L->separate）else的时候调用"<<endl;;
switch(PreCedeJudge(h->un.c,L->un.c))
{ case'<':

Push(optr,L);
L=L->next;

break;

case'=':

Pop(optr,h);
L=L->next;
break;
case'>':
Pop(optr,th);
Pop(opnd,y);
Pop(opnd,x);

c=Caculate(x->un.fl, th->un.c,y->un.fl);
z->un.fl=c;
Push(opnd, z);

break;
}//switch
cout<<"while()结束"<<endl;
}//if
cout<<"123";
system("pause");
}//while
cout<<"循环结束"<<endl;


Pop(opnd,h);
return h->un.fl;

}
//{
//return 0;
//}

void Run();
void main()
{
Run();

}
void Run()
{

Linklist sn;
Inital(sn);
//Inital(m);
// Inital(t);
Sqstack s1,s2;
// sn->un.c='k';
// m->separate=0;
// m->un.c='g';
BuildList(sn);
print(sn);

BuildEmpty(s1);
BuildEmpty(s2);
system("pause");
//Push(s,sn);
// Push(s,m);
// GetTop( s, t);
cout<< Caculation_process(sn,s1,s2);

}