给定字符串型的算术表达式，实现中缀转后缀并运算得出结果；
#ifndef STACK_H_INCLUDED
#define STACK_H_INCLUDED
#include <stdio.h>
#include <stdlib.h>
#include"stack.h"
#define SIZE 100
#define TYPE char
typedef struct Node* pNode;
typedef struct Node node;
typedef pNode Stack; char postfix[SIZE]; struct Node
{
TYPE data;
struct Node* next;
};
int isEmpty(Stack s);
void Pop(Stack s);
void Push(Stack s,TYPE element);
TYPE Top_of_stack(Stack s);
Stack CreatStack();
void makeEmpty(Stack s); Stack CreatStack()
{
Stack s=(Stack)malloc(sizeof(node));
s->next=NULL;
makeEmpty(s);
return s;
}
void makeEmpty(Stack s)
{
if(s==NULL)
printf("you need creat a stack at first");
while(!isEmpty(s))
Pop(s);
}
int isEmpty(Stack s)
{
return s->next==NULL;
}
void Pop(Stack s)
{
if(isEmpty(s))
printf("Stack is empty");
else
{
pNode temp=s->next;
s->next=s->next->next;
free(temp);
} }
void Push(Stack s,TYPE element)
{
pNode temp=(Stack)malloc(sizeof(node));
if(temp)
{
temp->data=element;
temp->next=s->next;
s->next=temp;
}
}
TYPE Top_of_stack(Stack s)
{
if(isEmpty(s))
{
printf("Stack is empty");
return ;
}
else
return s->next->data;
} #endif // STACK_H_INCLUDED
stack.h
#include <stdio.h>
#include <stdlib.h>
#include"stack.h"
#define SIZE 100 char postfix[SIZE]; // if op > instack push else pop;
// return the priority of operator of expression minus
//that of stack 栈外优先级减去栈内优先级
int priority(char op_of_expression,char ch_in_stack)
{
int op=;
int ch=;
if(op_of_expression=='+'||op_of_expression=='-')
op=;
else if(op_of_expression=='*'||op_of_expression=='/')
op=;
else if(op_of_expression=='(')
op=;
else
printf("wrong operator"); if(ch_in_stack=='+'||ch_in_stack=='-')
ch=;
else if(ch_in_stack=='*'||ch_in_stack=='/')
ch=;
else if(ch_in_stack=='(')
ch=;
else
printf("wrong operator"); return op-ch;
}
int isOperator(char ch)
{
switch (ch)
{
case'+':
case'-':
case'*':
case'/':
case'(':
case')':
return ;
break;
default:
return ;
break;
}
}
void Infix_to_Pofix(char* s)
{
int index=; char ch;
Stack stack=CreatStack();
makeEmpty(stack);
while((ch=*s)!='\0')
{
if(!isOperator(ch))
{
postfix[index++]=ch;
s++;
if(isOperator(*s)||*s=='\0')
postfix[index++]='_';
}
else
{
if(isEmpty(stack))
{
Push(stack,ch);
s++;
continue;
}
else
{
if(ch==')')
{
while(!isEmpty(stack)&&Top_of_stack(stack)!='(')
{
postfix[index++]=Top_of_stack(stack);
Pop(stack);
}
Pop(stack);
s++;
continue;
}
else if(priority(ch,Top_of_stack(stack))>)
{
Push(stack,ch);
s++;
continue;
}
else
{
while(!isEmpty(stack)&&priority(ch,Top_of_stack(stack))<=)
{
postfix[index++]=Top_of_stack(stack);
Pop(stack);
}
Push(stack,ch);
s++;
continue;
}
// else if(priority(ch,Tops))
}
} }
while(!isEmpty(stack))
{
postfix[index++]=Top_of_stack(stack);
Pop(stack);
}
//postfix[index++]='\0';
} int compute(char *str)
{
#undef TYPE
#define TYPE int
Stack s=CreatStack();
makeEmpty(s);
int temp_int;
while((*str)!='\0')
{ if(isdigit(*str))
{
Push(s,(int)atof(str));
//printf("ss%d",(int)atof(str));
while(((*str)!='_'))
{
str++;
}
str++;
}
else if(isOperator((*str)))
{
switch(*str)
{
case'*':
temp_int=Top_of_stack(s);
Pop(s);
//printf("%d\n",Top_of_stack(s));
temp_int*=Top_of_stack(s);
Pop(s);
Push(s,temp_int);
//printf("%d\n",Top_of_stack(s));
break;
case'-':
temp_int=Top_of_stack(s);
Pop(s);
//printf("%d\n",Top_of_stack(s));
temp_int=Top_of_stack(s)-temp_int;
Pop(s);
Push(s,temp_int);
//printf("%d\n",Top_of_stack(s));
break;
case'/':
temp_int=Top_of_stack(s);
Pop(s);
//printf("%d\n",Top_of_stack(s));
temp_int=Top_of_stack(s)/temp_int;
Pop(s);
Push(s,temp_int);
//printf("%d\n",Top_of_stack(s));
break;
case'+':
temp_int=Top_of_stack(s);
Pop(s);
//printf("%d\n",Top_of_stack(s));
temp_int+=Top_of_stack(s);
Pop(s);
Push(s,temp_int);
//printf("%d\n",Top_of_stack(s));
break;
default:
printf("wrong");
break;
}
str++;
} }
return temp_int;
} int main()
{
char ch[]="10+(3*6-8)/2";
Infix_to_Pofix(ch);
printf("%s\n",postfix);
//postfix="134.4";
// printf("%d\n",(int)atof("34_34*"));
printf("result：%d\n",compute(postfix)); return ;
}
中缀转后缀运算