带幂运算的中缀表达式转换后缀表达式问题
如题， 如 2^2^3 次表达式因是右结合，转换结果应为 2^8=256, 而不是4^3=64一个表达式中又含有左结合的普通运算和右结合的幂运算，该怎样实现程序呢，通过C语言实现。
此问题为 数据结构与算法分析中的问题。
已自行解决
我的方法是将其中的幂运算先转置，然后再按照正常左结合运算转换成后缀表达式即可：
//转置字符串
//转置字符串
void Transpose(char *p, char *q)
{
char tmp;
while (p < q)
{
if (*p != *q)
{
tmp = *p;
*p = *q;
*q = tmp;
}
p++;
q--;
}
}
//中缀表达式转换成后缀表达式
void InfixToPostfix(char *Infix, char *Postfix)
{
Stack S, tmp;
//OpNode op; //临时结构体指针变量,用于处理当前的字符
char c;
char *powBegin, *powEnd;
int level;
S = CreateStack();
MakeEmpty(S);
//将含有幂运算的表达式转换
//查找幂运算的头
powBegin = Infix;
while (*powBegin != '\0' && *powBegin != '^')
powBegin++;
while (*powBegin != Infix && *powBegin>='0' && *powBegin<='9' || *powBegin == '.')
powBegin--;
if(powBegin != Infix)
powBegin--;
//查找幂运算的尾
powEnd = powBegin;
while (*powEnd != '\0' && *powEnd>='0' && *powEnd<='9' || *powEnd == '.' || *powEnd == '^')
powEnd++;
powEnd--;
//转置幂运算表达式
Transpose(powBegin, powEnd);
printf("转置后：%s\n",Infix);
//p = Infix;
c = *Infix;
while ((c) != '\0')
{
//当字符是数字, 存入数组
if((c >= '0' && c <= '9' || c == '.'))
{
while(c >= '0' && c <= '9' || c == '.')
{
*Postfix++ = c;
c = *++Infix;
}
//插入分隔符
*Postfix++ = ' ';
}
//当前字符是'(',则进栈
if (c == '(')
{
level = -1; //定义优先级
Push(c, level, S);
}
//当前字符是 ')' 将栈元素弹出，直到'('
if (c == ')')
{
tmp = Top(S);
while (!IsEmpty(S) && tmp->e != '(')
{
//弹出元素,并存入后缀表达式数组
*Postfix++ = tmp->e;
Pop(S);
tmp = Top(S);
}
//弹出 '('
Pop(S);
}
if (c == '+' || c == '-')
{
level = 1; //定义优先级
if(IsEmpty(S))
//当前'+'进栈
Push(c, level, S);
else
{
tmp = Top(S);
//printf("符号：%c,level:%d\n",tmp->e,tmp->level);
//如果栈顶的符号不是'(' 且优先级不低于 '+' 号, 并且栈不为空,弹出
while (tmp->level >= level)
{
*Postfix++ = tmp->e;
Pop(S);
if(!IsEmpty(S))
tmp = Top(S);
else
break;
}
Push(c, level, S);
}
}
if (c == '*' || c == '/' || c == '%')
{
level = 2; //定义优先级
if(IsEmpty(S))
//当前'+'进栈
Push(c, level, S);
else
{
tmp = Top(S);
//如果栈顶的符号优先级不低于 当前符号, 并且栈不为空,弹出
while (!IsEmpty(S) && tmp->level >= level)
{
*Postfix++ = tmp->e;
Pop(S);
//if(!IsEmpty(S))
tmp = Top(S);
//else
//break;
}
Push(c, level, S);
}
}
if (c == '^')
{
level = 3;
if (IsEmpty(S))
Push(c, level, S);
else
{
tmp = Top(S);
while (!IsEmpty(S) && tmp->level >= level)
{
*Postfix++ = tmp->e;
Pop(S);
tmp = Top(S);
}
Push(c, level, S);
}
}
c = *++Infix;
}
while (!IsEmpty(S))
{
tmp = Top(S);
*Postfix++ = tmp->e;
Pop(S);
}
*Postfix = '\0';
}
[ 本帖最后由 jxlcs 于 2012-12-16 23:24 编辑 ]
