中缀表达式转换成后缀表达式

/* solution of convertion of infix to postfix */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct StackRecord
{
    char Operator[32];
    int TopIndex;
    int Capacity;
};

typedef struct StackRecord * Stack;

Stack CreateStack()
{
    Stack S = malloc(sizeof(struct StackRecord));
    S->TopIndex = -1;
    S->Capacity = 32;
}
inline int IsEmpty(Stack S){return S->TopIndex == -1;}
inline int IsFull(Stack S){return S->TopIndex == 31;}
void Push(Stack S,char Operator)
{
    // assuming S is not NULL, hha
    S->Operator[++S->TopIndex] = Operator;
}
char Pop(Stack S)
{
    if(IsEmpty(S)) return 0;
    return S->Operator[S->TopIndex--];
}
char Top(Stack S)
{
    if(IsEmpty(S)) return 0;
    return S->Operator[S->TopIndex];
}
int GetOperatorClass(char Operator)
{
    switch(Operator)
    {
    case '+': case '-':
        return 0;
    case '*': case '/':
        return 1;
    case '^':
        return 2;
    case '(':
        return 10;
    default:
        return -1;
    }
}
int IsOperator(char c)
{
    switch(c)
    {
    case '+':case '-':case '*':case '/':case '(':case ')':case '^':
        return 1;
    default:
        return 0;
    }
}
void PrintStack(Stack S)
{
    int i = 0;
    printf("Current Stack: ");
    for(; i <= S->TopIndex; ++i)
        printf("%c ", S->Operator[i]);
    printf("
");
}

int main()
{
    char *infix = "a+b*c^h^i+(d*e+f)*g";
    char postfix[128] = "";
    int len = strlen(infix);
    int i = 0;
    Stack S = CreateStack();
    char top;
    int j = 0;
    char curr;
    for(;i < len; ++i)
    {
        postfix[j] = '';
        printf("Current Output: %s
",postfix);
        curr = infix[i];
        if(IsOperator(curr))
        {
            PrintStack(S);
            if (curr == ')')
            {
                while('(' != (top = Pop(S)))
                    postfix[j++] = top;
                
            }else if(curr == '^')
            {
                top  = Top(S);
                while(top != '^' && 
                    (GetOperatorClass(curr) <= GetOperatorClass(top)) && 
                    top != '(')
                {
                    postfix[j++] = top; Pop(S);
                    top = Top(S);
                }
                Push(S,curr);
            }
            else
            {
                {
                    top = Top(S);
                    while((GetOperatorClass(curr) <= GetOperatorClass(top)) && top != '(')
                    {
                        postfix[j++] = top; Pop(S);
                        top = Top(S);
                    }
                }                
                Push(S,curr);
            }
            
        }
        else
            postfix[j++] = curr;
    }
    while((top = Pop(S)) != 0)
        postfix[j++] = top;
    postfix[j++] = '';
    printf("%s",postfix);
    return 0;
}
原文地址:https://www.cnblogs.com/jimmysue/p/3881171.html