【数据结构】中缀表达式转换后缀表达式（逆波兰式）

我不是女神ヾ 2022-06-17 03:37 159阅读 0赞

我的第一篇博文就是关于逆波兰式的，现在回头看感觉当时的代码太过混乱（不忍直视），在这里对当时的代码进行一次重构。

#include <stdio.h>
    #include <stdlib.h>
    #include "stack.h"
    #define MaxSize 30
    int Judge(int flag,char operater)
    {
        if(flag)
            switch(operater){
                case '+': return 3;
                case '-': return 3;
                case '*': return 5;
                case '/': return 5;
                case '(': return 1;
                case ')': return 6;
            }
        else
            switch(operater){
                case '+': return 2;
                case '-': return 2;
                case '*': return 4;
                case '/': return 4;
                case '(': return 6;
                case ')': return 1;
            }
    }
    void RPN(char *a)
    {
        int i = 0, j = 0;
        char b[MaxSize];
        LinkStack *Stack;
        Stack = CreateStack();
        while(a[i]){
            if(a[i] >= '0' && a[i] <= '9'){
                b[j++] = a[i];
                i++;
                continue;
            }
            while( !IsEmpty(Stack) && Judge(0,a[i]) < Judge(1,Stack->Next->Date))
                b[j++] = Pop(Stack);
            if(IsEmpty(Stack)){
                Push(Stack,a[i]);
                i++;
                continue;
            }
            else if(Judge(0,a[i]) > Judge(1,Stack->Next->Date))
                Push(Stack,a[i]);
            else if(Judge(0,a[i]) == Judge(1,Stack->Next->Date))
                Pop(Stack);
            i++;
        }
        while(!IsEmpty(Stack))
            b[j++] = Pop(Stack);
        b[j] = '\0';
        puts(b);
    }
    int main()
    {
        char a[MaxSize];
        gets(a);
        RPN(a);
        return 0;
    }

下面是头文件“stack.h”

#ifndef STACK_H_INCLUDED
    #define STACK_H_INCLUDED
    typedef struct Node{
        char Date;
        struct Node *Next;
    } LinkStack;
    LinkStack *CreateStack()
    {
        LinkStack *S;
        S = (LinkStack*)malloc(sizeof(struct Node));
        S->Next = NULL;
        return S;
    }
    int IsEmpty(LinkStack *S)
    {
        return(S->Next == NULL);
    }
    void Push(LinkStack *S, char item)
    {
        LinkStack *TmpCell;
        TmpCell = (LinkStack*)malloc(sizeof(struct Node));
        TmpCell->Date = item;
        TmpCell->Next = S->Next;
        S->Next = TmpCell;
    }
    char Pop(LinkStack *S)
    {
        LinkStack *FirstCell;
        char TopElem;
        if(IsEmpty(S)){
            printf("Stack is empty\n");
            return NULL;
        }
        else{
            FirstCell = S->Next;
            S->Next = FirstCell->Next;
            TopElem = FirstCell->Date;
            free(FirstCell);
            return TopElem;
        }
    }
    
    #endif // STACK_H_INCLUDED