带幂运算的中缀表达式转换后缀表达式问题

已自行解决

我的方法是将其中的幂运算先转置，然后再按照正常左结合运算转换成后缀表达式即可：

//转置字符串
//转置字符串
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 编辑 ]

哎呀 算法学到一半 又跑去学c++了 自己现在来看都要看半天
浪费了~