栈的应用实例——中缀表达式转换为后缀表达式

栈的应用实例——中缀表达式转换为后缀表达式声明：本程序读入一个中缀表达式，将该中缀表达式转换为后缀表达式并输出后缀表达式。

栈的应用实例——中缀表达式转换为后缀表达式注意：支持+、-、*、/、（），并且输入时每输入完一个数字或符号都要加一个空格，特别注意的是在整个表达式输入完成时也要加一个空格后再回车。这是该程序的一个不足之处，有待改进。

/* infix_to_postfix.c */

#include <stdio.h>
#include <errno.h>
#include <stdlib.h>
#include <unistd.h>

struct op_node
{
    char op;
    int level;
};
struct stack_record
{
    int capacity;
    int top_of_stack;
    struct op_node *array;    
};

struct stack_record * 
create_stack( int max_elements )
{
    struct stack_record *s;

    if(max_elements < 5)
    {
        printf(" stack size is too samll
");
        exit(0);
    }
    
    s = malloc(sizeof(struct stack_record));
    if(s == NULL)
    {
        perror("malloc");
        exit(1);
    }
    
    s->array = malloc(sizeof(struct op_node) * max_elements);
    if(s->array == NULL)
    {
        perror("malloc");
        exit(1);
    }

    s->capacity = max_elements;
    s->top_of_stack = -1;

    return s;
}

void 
push( struct op_node x, struct stack_record *s)
{
    if(s->top_of_stack + 1 == s->capacity)
    {    
        printf("full stack
");
        exit(0);
    }
    else
    {
        s->array[++s->top_of_stack] = x;
    }
}

struct op_node
top( struct stack_record *s)
{
    if(s->top_of_stack == -1)
    {
        printf("top : empty stack
");
        exit(1);
    }
    else
    {
        return s->array[s->top_of_stack];
    }
}

void
pop( struct stack_record *s)
{
    if(s->top_of_stack == -1)
    {
        printf("pop : empty stack
");
        exit(1);
    }
    else
    {
        s->top_of_stack--;
    }
}

struct op_node
top_and_pop( struct stack_record *s)
{
    if(s->top_of_stack == -1)
    {
        printf("top_and_pop : empty stack
");
        exit(1);
    }
    else
    {
        return s->array[s->top_of_stack--];
    }
}

int
main(void)
{  
    int i;
    static int j;
    char c;
    char data_string[100];
    char postfix_expression[100];
    struct stack_record *op_stack;
    struct op_node op1, op2;
    int flag;

    op_stack = create_stack(100);

    printf("Please input an infix-expression end with a space: 
");

    i = 0;
    j = 0;
    for(c = getchar(); c != '
'; c = getchar())
    {
        switch(c)
        {
            case '0':
            case '1':
            case '2':
            case '3':
            case '4':
            case '5':
            case '6':
            case '7':
            case '8':    
            case '9':
            case '.':
                flag = 1;
                data_string[i++] = c;
                break;
            case ' ':
                if(flag == 1)
                {
                    data_string[i] = '

栈的应用实例——中缀表达式转换为后缀表达式

相关推荐