[C / 자료구조] 3주차 실습문제 - 후위 표기 계산

후위 표기 계산

 

main (기본 코드)

#include "stack.h"
#include <string.h>
#include <stdio.h>


int eval(char* value) {
    int n = strlen(value);
    int v1, v2;
    char ch;

    stackType s;
    init_stack(&s);
    for (int i = 0; i < n; i++) {
        ch = value[i];
        if (ch != '+' && ch != '-' && ch != '/' && ch != '*') {
            ch = ch - '0';  // atoi
            push(&s, ch);
        }
        else {
            v2 = pop(&s);
            v1 = pop(&s);
            switch (ch) {
            case '+': push(&s, v1 + v2); break;
            case '-': push(&s, v1 - v2); break;
            case '*': push(&s, v1 * v2); break;
            case '/': push(&s, v1 / v2); break;
            }
        }
    }
    return pop(&s);
}

int main(void) {
    int result;
    char buf[20];
    printf(">>");
    scanf_s("%s", buf, 20);
    result = eval(buf);
    printf("Result: %d", result);
    return 0;
}

 

---

main (atoi 함수를 활용해서 토큰 단위로 입력받고 계산)

#include "stack.h"
#include <string.h>
#include <stdio.h>
#include <stdlib.h>

int eval() {
    double v1, v2;
    char ch;
    char buf[10];
    char temp;

    stackType s;
    init_stack(&s);
    while(1) {
        scanf_s("%s", buf, 10);
        if (strcmp(buf, "end") == 0) break;
        ch = buf[0];
        if (ch != '+' && ch != '-' && ch != '/' && ch != '*') {
            temp = atoi(buf);
            push(&s, temp);
            print_stack(&s, buf);
        }
        else {
            v2 = pop(&s);
            v1 = pop(&s);
            switch (ch) {
            case '+': push(&s, v1 + v2); break;
            case '-': push(&s, v1 - v2); break;
            case '*': push(&s, v1 * v2); break;
            case '/': push(&s, v1 / v2); break;
            }
            print_stack(&s, buf);
        }
    }
    return pop(&s);
}

int main(void) {
    double result;
    printf(">>");
    result = eval();
    printf("Result: %2.f", result);
    return 0;
}

 

 

두자릿수로 계산한 화면

 

 

stack.h

#include <stdio.h>
#include <string.h>
#include <stdio.h>

typedef double element;
typedef struct {
    element* stack;
    int top;
    int capacity;
} stackType;

void init_stack(stackType* s);
int is_full(stackType* s);
int is_empty(stackType* s);
void push(stackType*, element item);
element pop(stackType* s);
element peek(stackType* s);
void delete_stack(stackType* s);
void print_stack(stackType* s, const char* p);

 

stack.c

#include "stack.h"

void init_stack(stackType* s) {
    s->top = -1;
    s->capacity = 8;
    s->stack = (element*)malloc(sizeof(element) * s->capacity);
}

int is_full(stackType* s) {
    return (s->top >= (s->capacity - 1));
}

int is_empty(stackType* s) {
    return (s->top <= -1);
}

void push(stackType* s, element item) {
    if (is_full(s)) {
        s->capacity *= 2;
        s->stack = (element*)realloc(s->stack, s->capacity * sizeof(element));
        printf("\n*** Extend Array %d => %d ***\n\n", s->capacity / 2, s->capacity);
    }
    s->stack[++(s->top)] = item;
}

element pop(stackType* s) {
    if (is_empty(s)) {
        fprintf(stderr, "Stack Underflow\n");
        exit(1);
    }
    return s->stack[(s->top)--];
}

element peek(stackType* s) {
    if (is_empty(s)) {
        fprintf(stderr, "Stack Underflow\n");
        exit(1);
    }
    return s->stack[s->top];
}

void delete_stack(stackType* s) {
    free(s);
}

void print_stack(stackType* s, const char* ch) {
    printf("%-20.2f [stack]", ch);
    for (int i = 0; i <= s->top; i++) {
        printf("%.2f ", s->stack[i]);
    }
    printf("\n");
}