栈的应用二——中缀转后缀表达式

使用以上栈的声明和基本操作，只需把typedef int dataType;中的int改为char即可。

// 将字符分类
int classify(char c)
{
    switch (c)
    {
        case '(':
        case ')': return 2; // 表示界限符
        case '+':
        case '-':
        case '*':
        case '/': return 3; // 表示运算符
        default: return 1; // 表示操作数0-9
    }
}

// 将运算符划分优先级
int priority(char c)
{
    switch (c)
    {
        case '+':
        case '-': return 1;
        case '*':
        case '/': return 2;
    }
}

// 中缀表达式转后缀表达式的机器计算
/** 初始化一个栈，用于保存暂时无法确定运算顺序的运算符，依次扫描元素直到结束，
 * 1.遇到操作数直接加入后缀表达式；
 * 2.遇到左界限符则入栈，遇到右界限符则依次弹出栈中的运算符加入表达式，
 * 直到弹出左界限符，但左界限符不加入表达式；
 * 3.遇到运算符，依次弹出栈中优先级高于或等于当前运算符的所有运算符并加入后缀表达式，
 * 直到弹出左界限符或栈空。然后再把当前运算符入栈。
 * 4.当扫描的中缀表达式结束时，栈中的运算符依次出栈加入后缀表达式。
 **/
void convert(char m[], char r[])
{
    int i=0,j=0,type;
    seqStack stack;
    init(&stack);
    while (m[i])
    {
        type = classify(m[i]);
        if(type == 1) // 扫描到数字时
        {
            r[j++] = m[i];
        }
        else if(type == 2) // 扫描到界限符
        {
            if(m[i] == '(')
                push(&stack,m[i]);
            else
            {
                while (!empty(stack))
                {
                    if(read(stack) != '(')
                    {
                        r[j++] = read(stack);
                        pop(&stack);
                    }
                    else
                    {
                        pop(&stack); break;
                    }
                }
            }
        } else // 扫描到运算符
        {
            while(!empty(stack)&&read(stack)!='('&&classify(read(stack))==3)
            {
                if(priority(read(stack)) >= priority(m[i]))
                {
                    r[j++] = read(stack);
                    pop(&stack);
                } else break; // 如果栈中运算符优先级较低则退出循环
            }
            push(&stack,m[i]);
            r[j++] = ' '; // 每两个数之间加一个分隔符
        }
        i++;
    }
    while (!empty(stack))
    {
        r[j++] = read(stack);
        pop(&stack);
    }
}

int main()
{
    char c[] = "6/3+(5*6-2*7)/4";
    char r[MAX_SIZE]={};
    convert(c,r);
    int i=0;
    while (r[i])
    {
        printf("%c",r[i++]);
    }
    return 0;
}