为学日益，为道日损

《Data Structures and Algorithm Analysis in C》中文版中，第三章P54介绍了栈的实际应用，其中就有中缀到后缀的转换算法的详细描述和图示，该应用为编译器使用的一个算法，我使用Cmockery和前文中实现的栈数据结构来具体实现该算法，如下：

#include <stddef.h>
#include <stdarg.h>
#include <setjmp.h>
#include <cmockery.h>
#include "./stack_array.h"

int  calc_prio(char op)
{
    int rs;

    switch(op)
    {
    case '(':
        rs = 3;
        break;
    case '*':
        rs = 2;
        break;
    case '+':
        rs = 1;
        break;
    default:
        rs = 0;
        break;
    }

    return rs;
}

// convert an infix expression to a postfix expression
char* infix_to_postfix(char* buf)
{
    Stack stack = create();
   
    char* dest = (char*)malloc(MAX_LENGTH);
    char* ch = buf;
    char* ch_dest = dest;
    *dest = '\0';

    while(*ch)
    {
        switch(*ch)
        {
        case '(':
        case '+':
        case '*':
            {
                int cur_prio = calc_prio(*ch);
                int stack_prio;
                char top_ch;
               
                while (!is_empty(stack))
                {
                    top_ch = top(stack);
                    if (top_ch == '(')
                        break;                   
                    stack_prio = calc_prio(top_ch);
                    // 如果栈里的元素的优先级更高, 则将其pop出来
                    if (cur_prio<=stack_prio)
                        *ch_dest++ = pop(stack);
                    else
                        break;
                }
                push(stack, *ch);
            }        // end break
            break;
        case ')':
            {
                // 一直弹到'('为止
                char top_ch;
                if (is_empty(stack))
                {
                    printf("error format!\n");
                    break;
                }

                while (!is_empty(stack))
                {
                    top_ch = pop(stack);
                    if (top_ch != '(')
                        *ch_dest++ = top_ch;
                    else
                        break;
                }
            }
            break;
        default:    // 直接输出
            *ch_dest++ = *ch;
            break;
        }
        ch++;
    } // end while

    while(!is_empty(stack))
        *ch_dest++ = pop(stack);
    *ch_dest++ = '\0';

    printf("%s\n", dest);
    destroy(stack);
    return dest;
}

void infix_to_postfix_test(void **state)
{
    char src[] = "a+b*c+(d*e+f)*g";
    char dest[] = "abc*+de*f+g*+";
    char* tdest = infix_to_postfix(src);
    int i;

    for (i=0; i<strlen(dest); i++)
        assert_int_equal(dest[i], tdest[i]);
}

int main(int argc, char* argv[])
{
    const UnitTest tests[]={
        unit_test(infix_to_postfix_test),
    };

    return run_tests(tests);
};