#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<ctype.h>
#include<windows.h>
#define Max 1000
typedef struct node
{
char c;
struct node *next;
}Node;
//创建头节点
Node *create()
{
Node *head=(Node *)malloc(sizeof(Node));
head->c='\0';
head->next=NULL;
return head;
}
//入栈
void push(Node *top,const char ch)
{
Node *new_node=(Node*)malloc(sizeof(Node));
new_node->c=ch;
new_node->next=top->next;
top->next=new_node;
}
//出栈
int pop(Node *top,char *ch)
{
Node *tmp_nod=NULL;
if (top->next!=NULL)
{
tmp_nod=top->next;
top->next=tmp_nod->next;
*ch=tmp_nod->c;
free(tmp_nod);
return true;
}
else
return false;
}
//栈转字符串
char* Ntos(Node *ex)
{
char *postfix=(char*)malloc(sizeof(char)*Max),ch;
int i=0,j;
while (pop(ex,&ch))
*(postfix+i++)=ch;
*(postfix+i)='\0';
free(ex);
for(i=0,j=strlen(postfix)-1;i<j;i++,j--)
{
ch=*(postfix+i);
*(postfix+i)=*(postfix+j);
*(postfix+j)=ch;
}
return postfix;
}
void reorganize(char *infix)
{
int len=strlen(infix);
for(int i=0;i<len-1;i++)
if((i&&(('-'==infix[i]) && ('^'==infix[i-1] || '+'==infix[i-1] || '-'==infix[i-1] || '*'==infix[i-1] || '/'==infix[i-1] || '('==infix[i-1] || '['==infix[i-1] || '{'==infix[i-1]) && ('('==infix[i+1] || '['==infix[i+1] ||'{'==infix[i+1]))) || (i==0 && ('('==infix[i+1]||'['==infix[i+1]||'{'==infix[i+1])))
{
for(int j=len-1;j>=i;j--)
infix[j+1]=infix[j];
infix[i+1]='1',len++;
infix[len]='\0';
}
len=strlen(infix);
for(int i=0;i<len;i++)
if(((!isdigit(infix[i]))&&(!isalpha(infix[i]))&&'%'!=infix[i]&&'!'!=infix[i]&&'^'!=infix[i]&&infix[i]!='.'&&infix[i]!='_'&&infix[i]!='+'&&infix[i]!='-'&&infix[i]!='*'&&infix[i]!='/'&&infix[i]!='('&&infix[i]!=')'&&infix[i]!='['&&infix[i]!=']'&&infix[i]!='{'&&infix[i]!='}') || (i==0 && infix[0]=='+') || (i&&(('+'==infix[i]) && ('^'==infix[i-1] || '+'==infix[i-1] || '-'==infix[i-1] || '*'==infix[i-1] || '/'==infix[i-1] || '('==infix[i-1] || '['==infix[i-1] || '{'==infix[i-1]))))
{
for(int j=i;j<len-1;j++)
infix[j]=infix[j+1];
infix[len-1]='\0';
i--,len--;
}
len=strlen(infix);
for(int i=1;i<len;i++)
if( ((isalpha(infix[i]) || isdigit(infix[i])) && (infix[i-1]=='%' || infix[i-1]=='!')) || (infix[i]=='(' && infix[i-1]==')') || (infix[i]=='[' && infix[i-1]==']') || (infix[i]=='{' && infix[i-1]=='}') || (isalpha(infix[i]) && (isdigit(infix[i-1]) || isalpha(infix[i-1]))) || (isdigit(infix[i]) && isalpha(infix[i-1])) || ((infix[i]=='('|| infix[i]=='[' || infix[i-1]=='{' ) && (isalpha(infix[i-1]) || isdigit(infix[i-1]))) || ((infix[i-1]==')'|| infix[i-1]==']' && infix[i-1]=='}') && (isalpha(infix[i]) || isdigit(infix[i]))))
{
for(int j=len-1;j>=i;j--)
infix[j+1]=infix[j];
infix[i]='*',len++;
infix[len]='\0';
}
}
//中缀表达式to后缀表达式
char *postfix(char *infix)
{
Node *ex,*op;
ex=create();
op=create();
char ch;
int i=0;
while(*infix)
{
if(i==0&&infix[0]=='-')
push(ex,infix[0]);
else if(i&&(('-'==*infix) && ('+'==*(infix-1) || '-'==*(infix-1) || '*'==*(infix-1) || '/'==*(infix-1) || '('==*(infix-1) || '['==*(infix-1) || '{'==*(infix-1) || '^'==*(infix-1))))
push(ex,'-');
else if(isdigit(*infix) || '.'==*infix || isalpha(*infix) || '_'==*infix)
push(ex,*infix);
else if(*infix=='%'||*infix=='!')
{
push(ex,' ');
push(ex,*infix);
}
else if('('==*infix || '['==*infix || '{'==*infix)
push(op,*infix);
else if (')'==*infix || ']'==*infix || '}'==*infix)
while (pop(op,&ch))
{
if('('==ch || '['==ch || '{'==ch)break;
push(ex,' ');
push(ex,ch);
}
else if('*'==*infix || '/'==*infix)
{
push(ex,' ');
push(op,*infix);
}
else
{
while(pop(op,&ch))
{
if('('!=ch && '['!=ch && '{'!=ch)
{
push(ex,' ');
push(ex,ch);
}
else
{
push(op,ch);
break;
}
}
push(ex,' ');
push(op,*infix);
}
infix++,i++;
}
while(pop(op,&ch))
{
push(ex,' ');
push(ex,ch);
}
free(op);
return Ntos(ex);
}
int main()
{
char infix[Max],*post;
gets(infix);
reorganize(infix);
puts("整理,得:");
puts(infix);
post=postfix(infix);
printf("后缀表达式:\n%s\n",post);
system("PAUSE");
return 0;
}
#include<stdlib.h>
#include<string.h>
#include<ctype.h>
#include<windows.h>
#define Max 1000
typedef struct node
{
char c;
struct node *next;
}Node;
//创建头节点
Node *create()
{
Node *head=(Node *)malloc(sizeof(Node));
head->c='\0';
head->next=NULL;
return head;
}
//入栈
void push(Node *top,const char ch)
{
Node *new_node=(Node*)malloc(sizeof(Node));
new_node->c=ch;
new_node->next=top->next;
top->next=new_node;
}
//出栈
int pop(Node *top,char *ch)
{
Node *tmp_nod=NULL;
if (top->next!=NULL)
{
tmp_nod=top->next;
top->next=tmp_nod->next;
*ch=tmp_nod->c;
free(tmp_nod);
return true;
}
else
return false;
}
//栈转字符串
char* Ntos(Node *ex)
{
char *postfix=(char*)malloc(sizeof(char)*Max),ch;
int i=0,j;
while (pop(ex,&ch))
*(postfix+i++)=ch;
*(postfix+i)='\0';
free(ex);
for(i=0,j=strlen(postfix)-1;i<j;i++,j--)
{
ch=*(postfix+i);
*(postfix+i)=*(postfix+j);
*(postfix+j)=ch;
}
return postfix;
}
void reorganize(char *infix)
{
int len=strlen(infix);
for(int i=0;i<len-1;i++)
if((i&&(('-'==infix[i]) && ('^'==infix[i-1] || '+'==infix[i-1] || '-'==infix[i-1] || '*'==infix[i-1] || '/'==infix[i-1] || '('==infix[i-1] || '['==infix[i-1] || '{'==infix[i-1]) && ('('==infix[i+1] || '['==infix[i+1] ||'{'==infix[i+1]))) || (i==0 && ('('==infix[i+1]||'['==infix[i+1]||'{'==infix[i+1])))
{
for(int j=len-1;j>=i;j--)
infix[j+1]=infix[j];
infix[i+1]='1',len++;
infix[len]='\0';
}
len=strlen(infix);
for(int i=0;i<len;i++)
if(((!isdigit(infix[i]))&&(!isalpha(infix[i]))&&'%'!=infix[i]&&'!'!=infix[i]&&'^'!=infix[i]&&infix[i]!='.'&&infix[i]!='_'&&infix[i]!='+'&&infix[i]!='-'&&infix[i]!='*'&&infix[i]!='/'&&infix[i]!='('&&infix[i]!=')'&&infix[i]!='['&&infix[i]!=']'&&infix[i]!='{'&&infix[i]!='}') || (i==0 && infix[0]=='+') || (i&&(('+'==infix[i]) && ('^'==infix[i-1] || '+'==infix[i-1] || '-'==infix[i-1] || '*'==infix[i-1] || '/'==infix[i-1] || '('==infix[i-1] || '['==infix[i-1] || '{'==infix[i-1]))))
{
for(int j=i;j<len-1;j++)
infix[j]=infix[j+1];
infix[len-1]='\0';
i--,len--;
}
len=strlen(infix);
for(int i=1;i<len;i++)
if( ((isalpha(infix[i]) || isdigit(infix[i])) && (infix[i-1]=='%' || infix[i-1]=='!')) || (infix[i]=='(' && infix[i-1]==')') || (infix[i]=='[' && infix[i-1]==']') || (infix[i]=='{' && infix[i-1]=='}') || (isalpha(infix[i]) && (isdigit(infix[i-1]) || isalpha(infix[i-1]))) || (isdigit(infix[i]) && isalpha(infix[i-1])) || ((infix[i]=='('|| infix[i]=='[' || infix[i-1]=='{' ) && (isalpha(infix[i-1]) || isdigit(infix[i-1]))) || ((infix[i-1]==')'|| infix[i-1]==']' && infix[i-1]=='}') && (isalpha(infix[i]) || isdigit(infix[i]))))
{
for(int j=len-1;j>=i;j--)
infix[j+1]=infix[j];
infix[i]='*',len++;
infix[len]='\0';
}
}
//中缀表达式to后缀表达式
char *postfix(char *infix)
{
Node *ex,*op;
ex=create();
op=create();
char ch;
int i=0;
while(*infix)
{
if(i==0&&infix[0]=='-')
push(ex,infix[0]);
else if(i&&(('-'==*infix) && ('+'==*(infix-1) || '-'==*(infix-1) || '*'==*(infix-1) || '/'==*(infix-1) || '('==*(infix-1) || '['==*(infix-1) || '{'==*(infix-1) || '^'==*(infix-1))))
push(ex,'-');
else if(isdigit(*infix) || '.'==*infix || isalpha(*infix) || '_'==*infix)
push(ex,*infix);
else if(*infix=='%'||*infix=='!')
{
push(ex,' ');
push(ex,*infix);
}
else if('('==*infix || '['==*infix || '{'==*infix)
push(op,*infix);
else if (')'==*infix || ']'==*infix || '}'==*infix)
while (pop(op,&ch))
{
if('('==ch || '['==ch || '{'==ch)break;
push(ex,' ');
push(ex,ch);
}
else if('*'==*infix || '/'==*infix)
{
push(ex,' ');
push(op,*infix);
}
else
{
while(pop(op,&ch))
{
if('('!=ch && '['!=ch && '{'!=ch)
{
push(ex,' ');
push(ex,ch);
}
else
{
push(op,ch);
break;
}
}
push(ex,' ');
push(op,*infix);
}
infix++,i++;
}
while(pop(op,&ch))
{
push(ex,' ');
push(ex,ch);
}
free(op);
return Ntos(ex);
}
int main()
{
char infix[Max],*post;
gets(infix);
reorganize(infix);
puts("整理,得:");
puts(infix);
post=postfix(infix);
printf("后缀表达式:\n%s\n",post);
system("PAUSE");
return 0;
}