模拟计算后缀表达式的方式。
遇到符号则从栈中取出两个表达式或是数字进行重组成新的表达式，栈中存放当前符号计算出来的表达式
struct Node
{
char str[50];
int level;
PtrToNode next;
};
//Push 进栈
void Push(char *x, int level, Stack S)
{
PtrToNode tmpCell;
int i=0;
tmpCell = malloc(sizeof(struct Node));
if (tmpCell == NULL)
printf("Out of space!\n");
else
{
strcpy(tmpCell->str, x);
tmpCell->level = level;
tmpCell->next = S->next;
S->next = tmpCell;
}
}
//从栈弹出元素
void Pop(Stack S)
{
PtrToNode FirstCell;
if(IsEmpty(S))
printf("Empty stack\n");
else
{
FirstCell = S->next;
S->next = S->next->next;
free(FirstCell);
}
}
//返回栈顶元素所在结点的指针
Stack Top(Stack S)
{
if( !IsEmpty(S) )
return S->next;
printf("Empty stack\n");
return NULL;
}
//使栈为空
void MakeEmpty(Stack S)
{
if (S == NULL)
printf("Must Use CreeateStack first.\n");
else
while(!IsEmpty(S))
Pop(S);
}
//创建一个空栈
Stack CreateStack(void)
{
Stack S;
S = malloc(sizeof(struct Node));
if(S == NULL)
printf("Out of space!\n");
S->next = NULL;
MakeEmpty(S);
return S;
}
//测试栈是否空栈
int IsEmpty(Stack S)
{
return S->next == NULL;
}
//后缀表达式转成中缀表达式
void PostfixToInfix(char *In, char *Post)
{
int i,j,level;
char c,s[20],s2[20], exp[30];
Stack S,tmp;
S = CreateStack();
MakeEmpty(S);
c = *Post++;
while (c != '\0')
{
if (c >= '0' && c <= '9' || c == '.')
{
level = 0;
i=0;
while (c >= '0' && c <= '9' || c == '.')
{
s[i++] = c;
c = *Post++;
}
s[i] = '\0';
//数字字符串进栈
Push(s, level, S);
}
//符号处理
if (c == '+' || c == '-')
{
level = 1;
tmp = Top(S);
//如果栈顶优先级低，保存此表达式，并弹出
if (tmp->level <= level)
{
i=0;
j=0;
while (tmp->str[j]!='\0')
s[i++] = tmp->str[j++];
s[i] = '\0';
Pop(S);
}
tmp = Top(S);
if (tmp->level <= level)
{
i=0;
j=0;
while (tmp->str[j]!='\0')
s2[i++] = tmp->str[j++];
s2[i] = '\0';
Pop(S);
}
//用此运算符组成表达式
i=0;
j=0;
while(s2[j] != '\0')
exp[i++] = s2[j++];
exp[i++] = c;
j=0;
while(s[j] != '\0')
exp[i++] = s[j++];
exp[i] = '\0';
//表达式进栈
Push(exp, level, S);
}
if (c == '*' || c == '/' || c == '%')
{
level = 3;
tmp = Top(S);
//printf("top1: %s\n",tmp->str);
//printf("top2: %s\n",tmp->next->str);
//如果栈顶表达式优先级低，加括号并保存
if (tmp->level == 1 || tmp->level == 2)
{
i=0;
j=0;
s[i++] = '(';
while (tmp->str[j]!='\0')
s[i++] = tmp->str[j++];
s[i++] = ')';
s[i] = '\0';
//带括号的表达式的优先级置为 -1
tmp->level = -1;
//当前表达式整体优先级置为2
level = 2;
Pop(S);
}else
if (tmp->level <= level || tmp->level == -1)
{
i=0;
j=0;
while (tmp->str[j]!='\0')
s[i++] = tmp->str[j++];
s[i] = '\0';
Pop(S);
}
tmp = Top(S);
//如果栈顶表达式优先级低，加括号并保存
if (tmp->level ==1)
{
i=0;
j=0;
s2[i++] = '(';
while (tmp->str[j]!='\0')
s2[i++] = tmp->str[j++];
s2[i++] = ')';
s2[i] = '\0';
Pop(S);
}else
if (tmp->level <= level || tmp->level == -1)
{
i=0;
j=0;
while (tmp->str[j]!='\0')
s2[i++] = tmp->str[j++];
s2[i] = '\0';
Pop(S);
}
//用此运算符组成表达式
i=0;
j=0;
while(s2[j] != '\0')
exp[i++] = s2[j++];
exp[i++] = c;
j=0;
while(s[j] != '\0')
exp[i++] = s[j++];
exp[i] = '\0';
//表达式进栈
Push(exp, level, S);
}
if (c == '^')
{
level = 0;
tmp = Top(S);
//如果栈顶优先级低，保存此表达式，并弹出
if (tmp->level <= level)
{
i=0;
j=0;
while (tmp->str[j]!='\0')
s[i++] = tmp->str[j++];
s[i] = '\0';
Pop(S);
}
tmp = Top(S);
if (tmp->level <= level)
{
i=0;
j=0;
while (tmp->str[j]!='\0')
s2[i++] = tmp->str[j++];
s2[i] = '\0';
Pop(S);
}
//用此运算符组成表达式
i=0;
j=0;
while(s2[j] != '\0')
exp[i++] = s2[j++];
exp[i++] = c;
j=0;
while(s[j] != '\0')
exp[i++] = s[j++];
exp[i] = '\0';
//表达式进栈
Push(exp, level, S);
}
c = *Post++;
//putchar(c);
}
tmp = Top(S);
strcpy(In, tmp->str);
Pop(S);
}
2012-04-20 15:53
