中缀表达式转换

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 定义堆栈数据类型

typedef struct _symbol elem_t;
struct _symbol
{
    char symb; // 操作符

    int pri; // 优先级

};

// 定义堆栈类型

#define STACK_MAX_SIZE 50
typedef struct _stack stack_t;
struct _stack
{
    elem_t data[STACK_MAX_SIZE];
    int top_pt; // 栈顶指针

};

// 操作符号

enum{
    S_OPERATOR,
    S_DIGIT,
    S_BRACKET,
};

// 创建一个堆栈

stack_t *StackCreate(void)
{
    stack_t *s;
    s = (stack_t *)malloc(sizeof(stack_t));
    if (s==NULL)
    {
        printf("could not alloc memory for s");
        exit(1);
    }
    memset(&s->data,0,sizeof(elem_t)*STACK_MAX_SIZE);
    s->top_pt = 0;

    return s;
}

// 释放之前申请的内存

void StackDelete(stack_t *s)
{
    free(s);
}

// 检查堆栈是否为空或者为满

int StackIsEmpty(stack_t *s)
{
    return !s->top_pt;
}

int StackIsFull(stack_t *s)
{
    return s->top_pt == STACK_MAX_SIZE;
}

// 入栈

void StackPush(stack_t *s,elem_t d)
{
    if(StackIsFull(s))
    {
        printf("stack is full");
        StackDelete(s);
        exit(0);
    }
    
    s->data[s->top_pt] = d;
    s->top_pt++;
}

// 出栈

elem_t StackPop(stack_t *s)
{
    elem_t retval;
    if(StackIsEmpty(s))
    {
        printf("stack is empty");
        StackDelete(s);
        exit(0);
    }
    retval = s->data[s->top_pt-1];
    s->top_pt--;

    return retval;
}

// 查看返回栈顶数据

elem_t StackVeiwTop(stack_t *s)
{
    elem_t retval;
    if(StackIsEmpty(s))
    {
        printf("stack is empty");
        StackDelete(s);
        exit(0);
    }
    retval = s->data[s->top_pt-1];

    return retval;
}


// 中缀表达式转换为后缀表达式

void Nifix2Postfix(char *ni,char *po)
{
    stack_t *st;
    elem_t retval;
    elem_t param;
    int pri;
    int flag;
    
    // 生成符号栈

    st = StackCreate();
    
    // 符号栈的结束标志，一个最低优先级的符号

    param.pri = -1;
    param.symb = '@';
    StackPush(st,param);

    // 扫描输入字符串，直到'\0'为止

    while(*ni)
    {
        switch(*ni)
        {
            // 过滤掉多个空格

        case ' ':
            *po++=' ';
            while((*ni == ' ') && (*ni != '\0'))
                ni++;
            break;
            // +- 的优先级为1

        case '+':
        case '-':
            pri = 1;
            flag = S_OPERATOR;
            break;
            // * / 优先级为2

        case '*':
        case '/':
            pri = 2;
            flag = S_OPERATOR;
            break;
            // 如果是括号

        case '(':
        case ')':
            pri = 0;
            flag = S_BRACKET;
            break;
            // 其他的都看做数字，或者未知数变量

        default:
            // 如果之前的一个符号也是数字的话，那么之前输出的

            // 空格就多余了，操作指针返回一格

            if (flag == S_DIGIT)
                po--;
            flag = S_DIGIT;
            break;
        }

        // 如果扫描到的是操作符

        if (flag == S_OPERATOR)
        {
            // 查看堆栈最顶端的符号

            retval = StackVeiwTop(st);
            // 如果当前符号优先级小于等于堆栈的最顶端的

            // 符号的优先级的话，先出栈

            if(pri <= retval.pri)
            {
                // 出栈并且输出

                retval = StackPop(st);
                *po++ = retval.symb;
                *po++ = ' ';
            }
            // 将新符号入栈

            param.pri = pri;
            param.symb = *ni;
            StackPush(st,param);
        }
        
        // 如果扫描到的是括号

        if (flag == S_BRACKET)
        {
            // 左括号的话直接入栈

            if(*ni == '(')
            {
                param.pri = pri;
                param.symb = *ni;
                StackPush(st,param);
            } // 右括号的话将堆栈出栈

            else if(*ni == ')'){
                // 全部出栈，直到遇到左括号为止

                while(1)
                {
                    retval = StackPop(st);
                    if (retval.symb == '(')
                        break;
                    *po++ = retval.symb;
                    *po++ = ' ';
                }
            }
        }

        if (flag == S_DIGIT)
        {
            *po++ = *ni;
            *po++ = ' ';
        }

        ni++;
    }
    // 将堆栈的剩余内容全部出栈

    while((retval.symb = StackPop(st).symb) != '@')
    {
        *po++ = retval.symb;
        *po++ = ' ';
    }
    // 添加字符串结束标志，因为之前多输出了一个空格，所以这里去掉

    *(po-1)='\0';
    // 释放符号堆栈

    StackDelete(st);
}

int main(int argc,char *argv[])
{
    char *s1 = "(25+x)*(a*(a+b)+b)";
    char s2[50]={'\0'};
    
    // translate nifix to postfix expresstion

    Nifix2Postfix(s1,s2);

    printf("\nnifix : %s",s1);
    printf("\npostfix : %s",s2);

    return 0;
}