[자료구조][스택] 중위 수식 변환 프로그램 c구현

목차

 

자료구조에서 스택을 활용한 후위 수식과 관련된 문제를 풀고 공부하고자 한다.

 

 

 

기본 스택 구조체(단항 연산자때문에 rank를 따로 만들어주었다.)

typedef struct Node {
    char data;
    int rank;
    struct Node* next;
}Node;

typedef struct Stack {
    Node* head;
    Node* cur;
    int size;
}Stack;

 

 

스택의 필요한 ADT

// 스택 초기화 함수
void init(Stack* s) {
    s->size = 0;
    s->head = (Node*)malloc(sizeof(Node));
    s->head->next = NULL;
}

// 스택에 데이터를 추가하는 함수
void push(Stack* s, char data, int rank) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->rank = rank;
    newNode->next = NULL;

    newNode->next = s->head->next;
    s->head->next = newNode;
    s->size++;
}

//스택 pop 함수
char pop(Stack* s) {
    if (s->size == 0) {
        return;
    }
    Node* delnode = s->head->next;
    char del = delnode->data;
    if (s->size == 1) {
        s->head->next = NULL;
    }
    else
        s->head->next = s->head->next->next;
    free(delnode);
    s->size--;
    return del;
}

//스택 top 데이터 출력 함수
char peek(Stack* s) {
    if (s->size == 0) {
        return;
    }
    return s->head->next->data;
}

//스택 top 순위 출력 함수
int peekrank(Stack* s) {
    if (s->size == 0) {
        return;
    }
    return s->head->next->rank;
}

 

단항연산자를 포함한 순위를 계산하는 함수

int check(char s, char * str, int idx) {
    if (s == '!')
        return 6;
    else if ((s == '-' && idx == 0) || (s == '-' && str[idx - 1] == '*') || (s == '-' && str[idx - 1] == '/') || (s == '-' && str[idx - 1] == '+')) {
        return 6;
    }
    else if (s == '*' || s == '/')
        return 5;
    else if (s == '+' || s == '-')
        return 4;
    else if (s == '>' || s == '<')
        return 3;
    else if (s == '&')
        return 2;
    else if (s == '|')
        return 1;
    else
        return 0;
}

 

문제 1 main 함수 구현

int main() {
    Stack s;
    init(&s);
    int n, len = 0;
    char str[102];
    char array[102];
    scanf("%d", &n);
    getchar();
    
    for (int i = 0; i < n; i++) {
        scanf("%s", str);
        getchar();
        len = 0;
        for (int j = 0; j < strlen(str); j++) {
            if (str[j] >= 'A' && str[j] <= 'Z') { //피연산자는 그냥 배열에 넣어준다
                array[len++] = str[j];
            }
            else if (str[j] == '(')  //괄호는 순위가 0이므로 바로 넣어준다 
                push(&s, str[j], 0);
            else if (str[j] == ')') {   // 닫는 괄호가 나올 시
                while (peek(&s) != '(') {  //여는 괄호가 나올때까지 배열에 추가해준다
                    array[len++] = pop(&s);
                    if (array[len - 1] == '|')
                        array[len++] = '|';
                    else if (array[len - 1] == '&')
                        array[len++] = '&';
                }

                pop(&s);  //여는 괄호 제거
            }
            else {
                if (str[j] == '|' || str[j] == '&')  //두개씩 입력되므로 ++
                    j++;
                while (s.size != 0 && peekrank(&s) >= check(str[j], str, j)) {
                        // 스택 top이 순위가 더 높거나 같으면 계속해서 배열에 추가해준다
                        array[len++] = pop(&s);
                        if (array[len - 1] == '|')
                            array[len++] = '|';
                        else if (array[len - 1] == '&')
                            array[len++] = '&';
                 }
                push(&s, str[j], check(str[j], str, j)); //스택에 넣어준다
            }
        }
        while (s.size != 0) {  //스택이 빌때까지 나머지 연산자를 다 넣어준다
            array[len++] = pop(&s);
            if (array[len - 1] == '|')
                array[len++] = '|';
            else if (array[len - 1] == '&')
                array[len++] = '&';
        }

        array[len] = '\0';  //끝에 null문자열 추가
        printf("%s\n", array);
    }
}

 

 

문제 2  main함수 구현

int operator(char op, int x, int y) {
    switch (op) {
    case '+':
        return x + y;
    case '-':
        return x - y;
    case '*':
        return x * y;
    case '/':
        return x / y;
    }
}

int main() {
    Stack s;
    init(&s);
    int n, result=0;
    char str[102];
    char array[102];
    scanf("%d", &n);
    getchar();
    for (int i = 0; i < n; i++) {
        scanf("%s", str);
        getchar();
        for (int j = 0; j < strlen(str); j++) {
            if (str[j] >= '0' && str[j] <= '9')
                push(&s, str[j]-'0');
            else {
                int a = pop(&s);
                int b = pop(&s);
                push(&s, operator(str[j], b, a));
            }
        }
        printf("%d\n", pop(&s));
    } 
}