中缀表达式转换为后缀表达式&后缀表达式的计算

《数据结构与算法分析》练习题系列。
中缀转换成后缀的算法书上写的非常详细了，在做练习题时我就按照书上的思路用c写了一遍，但有个小错误没注意，所以一直报错，调了半天，终于好了。。。
废话不多说，程序是用栈的数组形式实现的，结构体是这样的：

#define Error -1

struct StackRecord;
typedef struct StackRecord *Stack;
typedef char ElementType;

struct StackRecord
{
int Capacity;
int TopOfStack;
    ElementType *Array;
};

程序已修改，添加了幂操作符。
一般的操作符运算顺序是从左到右，比如对减法：a-b-c，是先算a-b，然后用结果-c，但幂运算的顺序是从右到左，比如2^3^2，结果是512而不是64（我用手机算的是512，后来拿计算器算了一下发现是64，擦汗。。。但为了区分一般的运算符，我们假设‘^’是从右到左运算的，否则就没啥意思了，我们的目的是探究输入条件变化时算法的变化不是吗，嘿嘿。。。），所以‘^’运算符在进栈时，如果栈顶符号也是‘^’，则不弹出，而是进栈。
下面是中缀转换成后缀的代码：

/*中缀表达式转换为后缀表达式*/
char(*InfixToPostfix(char *str))[100]
{
int count;
char(*output)[100];
    Stack S;
    S = CreatStack(100);//创建一个堆栈

count = 0;//输出符号流计数
    output = calloc(100, sizeof(char));//为输出符号流创建空间
for (int i = 0; i < 100; i++)//初始化
        *output[i] = '\0';
/*主程序*/
for (int i = 0; str[i] != '\0'; i++)
    {
if (str[i] != '+' && str[i] != '-' && str[i] != '*' && str[i] != '/' && str[i] != '(' && str[i] != ')' && str[i] != '^')
            *output[count++] = str[i];
else
        {
/*如果堆栈空就直接进栈*/
if (IsEmpty(S))
                Push(str[i], S);
/*碰到')'符号，就把堆栈中符号连续弹出，直到遇见'('符号停止*/
else if (str[i] == ')')
            {
while (Top(S) != '(')
                {
                    *output[count++] = TopAndPop(S);//弹出栈顶符号
if (IsEmpty(S))
                    {
                        printf("Error!\n");
                        exit(-1);
                    }
                }
                Pop(S);
            }
/*如果当前符号优先级高于栈顶符号，当前符号进栈*/
else if (Priority(str[i], Top(S)))
                Push(str[i], S);
/*否则看下面*/
else
            {
/*注意：符号'('优先级虽然最高，但除非遇到')'，否则不会弹出！*/
if (Top(S) == '(' || (str[i] == '^' && Top(S) == '^'))
                    Push(str[i], S);
else
                {
/*当前符号优先级不高于栈顶符号，则栈顶符号弹出，当前符号入栈*/
/*这里考虑了栈顶符号弹出后，堆栈中的下一个符号和当前符号优先级相同的情况*/
while (!IsEmpty(S) && !Priority(str[i], Top(S)) && Top(S) != '(')
                        *output[count++] = TopAndPop(S);        
                    Push(str[i], S);
                }
            }
        }
    }
/*将剩余堆栈符号全部弹出*/
while (!IsEmpty(S))
    *output[count++] = TopAndPop(S);

return output;
}

错误原因就在50行，我在前面的注释还给自己提醒了：符号’(‘优先级虽然最高，但除非遇到’)’，否则不会弹出，但是还是大意了，忘了&& Top(S) != '('，无奈.jpg。。

这是里面用到的一个优先级判断函数（添加了幂操作符）：

int Priority(char x, char y)
{
    int numx, numy;

    switch (x)
    {
case '(':numx = 0; break;
case '^':numx = 1; break;
case '*':
case '/':numx = 2; break;
case '+':
case '-':numx = 3; break;
    }

    switch (y)
    {
case '(':numy = 0; break;
case '^':numy = 1; break;
case '*':
case '/':numy = 2; break;
case '+':
case '-':numy = 3; break;
    }

return numx < numy ? 1 : 0;

}

main函数：

int main(void)
{
    char(*ans)[100];
    char str[100];
while (scanf_s("%s", str, sizeof(str)) != NULL)
    {
        ans = InfixToPostfix(str);
printf("ans = ");
for (int i = 0; *ans[i] != '\0'; i++)
printf("%c", *ans[i]);
printf("\n");
    }

system("pause");
}

运行结果：

下面是计算后缀表达式的代码（没有加幂操作符）：

/*计算后缀表达式*/
int CalPostfix(char *str)
{
    int ans, temp;
    Stack S;
    S = CreatStack(100);

for (int i = 0; str[i] != '\0'; i++)
    {
if (str[i] != '+' && str[i] != '-' && str[i] != '*' && str[i] != '/')
            Push((int)(str[i] - '0'), S);
else
switch (str[i])
            {
case '+': {
                temp = TopAndPop(S);
if (temp == Error)
return Error;
else
                    ans = temp;
                temp = TopAndPop(S);
if (temp == Error)
return Error;
else
                    ans = temp + ans;
                Push(ans, S);
            }break;

case '-': {
                temp = TopAndPop(S);
if (temp == Error)
return Error;
else
                    ans = temp;
                temp = TopAndPop(S);
if (temp == Error)
return Error;
else
                    ans = temp - ans;
                Push(ans, S);
            }break;

case '*': {
                temp = TopAndPop(S);
if (temp == Error)
return Error;
else
                    ans = temp;
                temp = TopAndPop(S);
if (temp == Error)
return Error;
else
                    ans = temp * ans;
                Push(ans, S);
            }break;

case '/': {
                temp = TopAndPop(S);
if (temp == Error)
return Error;
else
                    ans = temp;
                temp = TopAndPop(S);
if (temp == Error)
return Error;
else
                    ans = temp / ans;
                Push(ans, S);
            }break;

            }
    }

    ans = TopAndPop(S);
if (IsEmpty(S))
return ans;
else
return Error;
}

结构体形式有所变化，为了能计算具体的数，把ElementType改成了int。

struct StackRecord;
typedef struct StackRecord *Stack;
typedef int ElementType;

struct StackRecord
{
int Capacity;
int TopOfStack;
    ElementType *Array;
};