论坛 › 数据结构与算法 › 中缀转后缀(Infix2Postfix.c)

spy 发表于 2015-12-18 22:46:57

中缀转后缀(Infix2Postfix.c)

本帖最后由 spy 于 2015-12-19 10:18 编辑

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#include <ctype.h>
#include <conio.h>
#include <math.h>

/*
算法的基本思想是:
        顺序扫描键盘缓冲区中输入的中缀表达式，读到操作数时，直接将其存放至操作数队列
        读到运算符时，将操作符栈中所有优先级高于或等于该运算符的运算符弹出栈，
        并将其存放至操作数队列，然后在将读入的运算符入栈
        当读入左括号时直接入栈；
        当读到右括号时，将与靠近栈顶的第一个左括号之间的运算符全部依次弹出栈，存放至输出队列
*/

struct StackNode
{
        char data;
        struct StackNode* next;
};
void Push(struct StackNode** top, char data);
char Pop(struct StackNode** top);
char GetTop(struct StackNode* top);

struct QueueNode
{
        float data;
        struct QueueNode* next;
};
void InitQueue(struct QueueNode** front, struct QueueNode** rear);
void EnQueue(struct QueueNode** rear, float data);
float DeQueue(struct QueueNode* front, struct QueueNode** rear);
void QueueTraverse(struct QueueNode* front);
void DestroyQueue(struct QueueNode** front, struct QueueNode** rear);

int Priority(char op);

void main()
{
        // 保存操作符的栈
        struct StackNode* top = NULL;
        // 队列中要存放的是转换后的逆波兰表达式就是后缀表达式
        struct QueueNode* front = NULL;
        struct QueueNode* rear = NULL;
        float num;
        char ch, e;
        InitQueue(&front, &rear);
        printf("请输入中缀表达式, 以回车键结束输入:\n");
        do
        {
                scanf("%c", &ch);
                switch ( ch )
                {
                case ' ': break;       // 过滤掉空格
                // 检测到键盘缓冲区中有数字开始的字符
                case '0':
                case '1':
                case '2':
                case '3':
                case '4':
                case '5':
                case '6':
                case '7':
                case '8':
                case '9':
                        ungetc(ch, stdin);         // pay attention !
                        scanf("%f", &num);         // 以浮点数的格式从键盘缓冲区获得一个操作数(整数同样也可以读取)
                        EnQueue(&rear, num); break;         // 将读取到的操作数入队
                // 碰到左括号，先放入操作符栈
                case '(':
                        Push(&top, ch); break;
                // 碰到有括号, 由于括号隔离了优先级, 则需要先计算左右括号之间的表达式
                case ')':
                case '\n':// pay attention! 加'\n'是考虑到读取到最后的一个结束字符时栈中还有一个操作符并没有参与运算
                        // top时刻指向操作符的栈顶，当栈中存在操作符且操作符位于左右括号之间时才将栈中的操作符弹出栈，然后放入操作数队列
                        while ( top && ( e=Pop(&top), e!='(' ) )
                        {
                                EnQueue(&rear, e);
                        }
                        break;
                // 四则运算
                case '+':
                case '-':
                case '*':
                case '/':
                        // 判读优先级，如果当前读入的操作符优先级低于栈顶操作符优先级则说明栈顶操作符的优先级别高，将它弹出栈并入操作数队列
                        while ( Priority(ch) <= Priority(GetTop(top)) )
                        {
                                e = Pop(&top);
                                EnQueue(&rear, e);
                        }
                        Push(&top, ch);
                        break;
                default:
                        printf("表达式非法!\n");
                        exit(0);
                }
        } while( ch!='\n' );

        // 此时队列中存放的是转换好的逆波兰表达式（后缀表达式），有了逆波兰表达式就可以进一步的求出表达式的值了（不难的求的）^-^
        QueueTraverse(front);

        DestroyQueue(&front, &rear);

        _getch();

}

int Priority(char op)
{
        switch ( op )
        {
        case '(':
        case '#':
                return 0;
        case '-':
        case '+':
                return 1;
        case '*':
        case '/':
                return 2;
        default:
                return -1;
        }
}

void Push(struct StackNode** top, char ch)
{
        struct StackNode* p = (struct StackNode*)malloc(sizeof(struct StackNode));
        p->data = ch;
        p->next = *top;
        *top = p;
}
char Pop(struct StackNode** top)
{
        struct StackNode* p = *top;
        char e;
        if ( p == NULL )
        {
                printf("下溢!\n");
                exit(0);
        }
        e = p->data;
        *top = p->next;
        free(p);
        return e;
}

char GetTop(struct StackNode* top)
{
        if ( top == NULL )
        {
                return -1;
        }
        return top->data;
}

void InitQueue(struct QueueNode** front, struct QueueNode** rear)
{
        struct QueueNode* p = (struct QueueNode*)malloc(sizeof(struct QueueNode));
        p->next = NULL;
        *front = *rear = p;
}

void EnQueue(struct QueueNode** rear, float e)
{
        if ( *rear == NULL )
        {
                printf("队列已被销毁或者还没有被初始化, 请初始化队列!");
        }
        else
        {
                struct QueueNode* p = (struct QueueNode*)malloc(sizeof(struct QueueNode));
                p->data = e;
                p->next = NULL;
                (*rear)->next =p;
                *rear = p;
        }
}

float DeQueue(struct QueueNode* front,struct QueueNode** rear)
{
        float e;
        if ( front == NULL )
        {
                printf("队列已被销毁或者还没有被初始化, 请初始化队列!\n\n");
        }
        else
        {
                if ( front == *rear )
                {
                        printf("队列为空, 无法出队!\n\n");
                }
                else
                {
                        struct QueueNode* p = front->next;
                        e = p->data;
                        front->next = p->next;
                        if ( p == *rear )
                        {
                                *rear = front;
                        }
                        free(p);
                }
        }
        return e;
}

void QueueTraverse(struct QueueNode* front)
{
        struct QueueNode* p = front;
        if ( p == NULL )
        {
                printf("队列已被销毁或者还没有被初始化, 请初始化队列!");
        }
        else
        {
                if ( p->next == NULL )
                {
                        printf("队列为空!");
                }
                else
                {
                        printf("队列中的元素为: ");
                        while ( p->next != NULL )
                        {
                                p = p->next;
                                switch ( (char)p->data )
                                {
                                case '+':
                                case '-':
                                case '*':
                                case '/':
                                        printf("%c ", (char)p->data); break;
                                default:
                                        printf("%f ", p->data);
                                }
                        }
                }
        }
        printf("\n");
}

void DestroyQueue(struct QueueNode** front, struct QueueNode** rear)
{
        while( *front )
        {
                *rear = (*front)->next;
                free(*front);
                *front = *rear;
        }
}

misys 发表于 2015-12-19 00:37:34

^-^

lewisyixin 发表于 2015-12-19 22:40:21

非常感谢楼主

lewisyixin 发表于 2015-12-21 23:30:48

非常感谢

lewisyixin 发表于 2015-12-22 23:07:40

感谢分享

spy 发表于 2015-12-23 13:36:18

lewisyixin 发表于 2015-12-21 23:30
非常感谢

很高心能帮助到你^_^

查看完整版本: 中缀转后缀(Infix2Postfix.c)