#include "stdafx.h"
#include "string.h"
#define N -1
#include
#define LEN sizeof(struct student)
struct student
{
int num; //表达式的值
char date; //表达式的符号
struct student * next;
};
struct student *head1() //得到栈表达式中数据的top指针
{
struct student *p1;
p1=(struct student*)malloc(sizeof(struct student));
p1->next=NULL;
return p1;
}
void get1(struct student *p1) //p1相当于top,建立表达式数据的栈
{
struct student *top,*h;
int x;
top=p1; //p2相当于单链表的头结点
printf("请输入你的数据(该数据从左往右是依次算式的数字）,并在末尾输入-1以示结束\n");
scanf("%d",&x );
while(x!=N)
{
h=(struct student*)malloc(sizeof(struct student));
h->num=x;
h->next =top->next;
top->next=h; //生成新结点,将读入数据存放到新结点的数据域中,将该新结点插入到链表的前端
scanf("%d",&x );
}
}
struct student *head2() //得到栈表达式中字符的top指针
{
struct student *p2;
p2=(struct student*)malloc(sizeof(struct student));
p2->next=NULL;
return p2;
}
void get2(struct student *p2) //p1相当于top,建立表达式字符的栈
{
struct student *top,*h;
char x;
char b;
top=p2; //p2相当于单链表的头结点
printf("请输入你的数据(该数据是算式的运算符),并在末尾输入!以示结束\n");
scanf("%c",&x );
b=x;
while(b!='!')
{
h=(struct student*)malloc(sizeof(struct student));
h->date=x;
if(h->date==10)
{
h=(struct student*)malloc(sizeof(struct student));
scanf("%c",&x);
h->date=x;
h->next =top->next;
top->next=h;
}
else
{
h->next =top->next;
top->next=h; //生成新结点,将读入数据存放到新结点的数据域中,将该新结点插入到链表的前端
scanf("%c",&x );
}
b=h->date;
scanf("%c",&x);
}
top->next=top->next->next;
}
void put1(struct student *p1) //输出栈表达式的数据
{
struct student *p3;
p3=p1;
printf("数字栈中的数据有:\n");
while(p3->next!=NULL)
{
printf("%d",p3->next->num );
p3=p3->next;
if(p3->next!=NULL)
{
printf("->");
}
}
printf("\n");
}
void put2(struct student *p2) //输出栈表达式的数据
{
struct student *p3;
p3=p2;
printf("字符栈的数据有:\n");
while(p3->next!=NULL)
{
printf("%c",p3->next->date );
p3=p3->next;
if(p3->next!=NULL)
{
printf("->");
}
}
printf("\n");
}
int pop1(struct student *p1) //表达式数据弹栈
{
struct student *top,*p,*a;
top=p1;
int m;
m=top->next ->num ;
a=top->next ;
p=top->next ;
p=p->next ;
top->next =p;
delete a;
return m;
}
void push1(struct student *p1,int num) //表达式数据压栈
{
struct student *top,*n,*p;
top=p1;
n=(struct student*)malloc(sizeof(struct student));
n->num =num;
n->next=top->next ;
top->next =n;
p=top->next ;
while(p!=NULL)
{
printf("%d",p->num );
p=p->next;
if(p!=NULL)
{
printf("->");
}
}
printf("\n");
}
char pop2(struct student *p2) //表达式字符弹栈
{
struct student *top,*p,*a;
top=p2;
char m;
m=top->next ->date ;
a=top->next ;
p=top->next ;
p=p->next ;
top->next =p;
delete a;
return m;
}
void push2(struct student *p2,char date) //表达式字符压栈
{
struct student *top,*n,*p;
top=p2;
n=(struct student*)malloc(sizeof(struct student));
n->date =date;
n->next=top->next ;
top->next =n;
p=top->next ;
while(p!=NULL)
{
printf("%c",p->date );
p=p->next;
if(p!=NULL)
{
printf("||");
}
}
printf("\n");
}
int opreate(int num1,int num2,char num3)
{
int a,b,sum;
a=num1;
b=num2;
if(num3==43)
{
sum=a+b;
}
if(num3==95)
{
sum=b-a;
}
if(num3==42)
{
sum=a*b;
}
return sum;
}
int main()
{
struct student *top1,*top2;
char m,n,q;
int sum,a,b;
top1=head1(); //得到栈表达式的数据的栈顶指针
top2=head2(); //得到栈表达式的字符的栈顶指针
get1(top1); //建立表达式的数据栈
get2(top2); //建立表达式的字符栈
printf("请输入运算字符\n");
scanf("%c",&m);
while(m!='#')
{
n=pop2(top2);
if(n>m) //比较表达式字符栈的栈顶元素和输入的大小
{
push2(top2,n);
push2(top2,m);
printf("请输入运算字符\n");
scanf("%c",&m);
}
else if(n {
if(m==42||m==43||m==95)
{
a=pop1(top1);
b=pop1(top1);
push1(top1, opreate(a,b,m));
push2(top2,n);
scanf("%c",&m);
}
else
{
a=pop1(top1);
b=pop1(top1);
n=pop2(top2);
push1(top1, opreate(a,b,n));
scanf("%c",&m);
}
}
else if(n==m)
{
scanf("%c",&m);
}
scanf("%c",&m);
}
printf("%d",pop1(top1));
printf("\n");
return 0;
}
