[데이터 구조] 접미사 표현 식 전환 접미사 표현 식 (역 폴란드 식)

나의 첫 번 째 박문 은 바로 역 폴란드 식 에 관 한 것 이다. 지금 돌 이 켜 보면 그 당시 의 코드 가 너무 혼 란 스 러 웠 다 (차 마 직시 할 수 없다). 여기 서 그 당시 의 코드 를 재 구성 했다.
#include 
#include 
#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
"
); return NULL; } else{ FirstCell = S->Next; S->Next = FirstCell->Next; TopElem = FirstCell->Date; free(FirstCell); return TopElem; } } #endif // STACK_H_INCLUDED

좋은 웹페이지 즐겨찾기