#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<stdbool.h>
#define MAX 150
typedef struct node{
char date;
struct node *next;
} LinkStake;
typedef struct node2{
double date;
struct node *next;
} Stake;
typedef struct body{
char date[MAX];
int j;
} Body;
LinkStake *CreatStake();//建立空栈
int IsEmpty(LinkStake *s);//判断空栈
void Push(char fuhao, LinkStake *s, Body *p);//压栈
int Judge(bool flag, char c);//判断优先级
LinkStake *CreatStake()
{
LinkStake *s;
s=malloc(sizeof(struct node));
s->next = NULL;
return s;
}
int IsEmpty(LinkStake *s)
{
return(s->next == NULL);
}
void Push(char fuhao, LinkStake *s, Body *p)
{
while(s->next != NULL && Judge(false,fuhao)<Judge(true,s->next->date)){
LinkStake *t;
printf("%c ", s->next->date);
p->date[p->j] = s->next->date;
p->j++;
t = s->next;
s->next = t->next;
free(t);
}
if(IsEmpty(s)){
LinkStake *tmp;
tmp = malloc(sizeof(struct node));
tmp->date = fuhao;
tmp->next = s->next;
s->next = tmp;
}
else if(Judge(false,fuhao)>Judge(true,s->next->date)){
LinkStake *tmp;
tmp = malloc(sizeof(struct node));
tmp->date = fuhao;
tmp->next = s->next;
s->next = tmp;
}
else if(Judge(false,fuhao) == Judge(true,s->next->date)){
LinkStake *t;
t = s->next;
s->next = t->next;
free(t);
}
}
int Judge(bool flag, char c)
{
if(c == '+' || c == '-')
if(flag) return 3;
else return 2;
else if(c == '*' || c == '/')
if(flag) return 5;
else return 4;
else if(c == '(')
if(flag) return 1;
else return 6;
else if(c == ')')
if(flag) return 6;
else return 1;
else return 0;
}
void PushStake(double c, LinkStake* s)
{
Stake *tmp;
tmp = malloc(sizeof(struct node2));
tmp->date = c;
tmp->next = s->next;
s->next = tmp;
}
double PopStake(LinkStake *s)
{
Stake *t;
double c;
t = s->next;
c = t->date;
s->next = t->next;
free(t);
return c;
}
int main()
{
int i = 0;
LinkStake *head;
Body *p = malloc(sizeof(struct body));
char s[MAX];
head = CreatStake();
p->j = 0;
// printf("请输入中缀表达式;\n");
scanf("%s",s);
// printf("转换为后缀表达式: \n");
while(s[i]){
if(s[i]>='0' && s[i]<='9'){
printf("%c ", s[i]);
p->date[p->j] = s[i];
p->j++;
}
else Push(s[i],head,p);
i++;
}
while(head->next != NULL){
printf("%c ", head->next->date);
p->date[p->j++] = head->next->date;
p->j++;
LinkStake *t;
t = head->next;
head->next = t->next;
free(t);
}
printf("%c",8);
printf("\n");
Stake *stake;
double sum = 0.0, a, b;
double sum1=0.0;
int length;
length = strlen(s);
stake = (Stake*)malloc(sizeof(struct node2));
stake->next = NULL;
for(i = 0; i < p->j; i++){
if(p->date[i]>='0' && p->date[i]<='9')
{
if(length>1)
PushStake((double)(p->date[i]-'0'), stake);
else {
sum1=p->date[i];
printf("%.3lf",sum1-'0');goto end;
}
}
else if(p->date[i]=='+'){
if(length>1){
b = PopStake(stake);}
else b=0;
a = PopStake(stake);
sum = a+b;
PushStake(sum, stake);
}
else if(p->date[i]=='-'){
if(length>1){
b = PopStake(stake);}
else b=0;
a = PopStake(stake);
sum = a-b;
PushStake(sum, stake);
}
else if(p->date[i]=='*'){
if(length>1){
b = PopStake(stake);}
else b=1;
a = PopStake(stake);
sum = a*b;
PushStake(sum, stake);
}
else if(p->date[i]=='/'){
if(length>1){
b = PopStake(stake);}
else b=1;
a = PopStake(stake);
sum = a/b;
PushStake(sum, stake);
}
}
printf("%.3lf", sum);
end:
return 0;
}