[C] 후위 표기법 스택 계산기

후위 표기법 스택계산기

• 숫자를 만나면 스택에 push
• 연산자를 만나면 스택에서 두개를 pop해서 계산, 결과를 다시 push
• 최종 결과는 모두 마친 뒤 스택에 남아있는 값

$ ./run "100 200 + 2 / 5 * 7 +"
expression: 100 200 + 2 / 5 * 7 +
result: 757

int stack_calculator(struct stack *stk, char *exp)
{
	char *token = strtok(exp, " "); // using strtok() for seperating token from exp

	while (token != NULL) {
		if (isdigit(token[0])) { //NOTE: number token always begin with digit
			int num = 0;
			sscanf(token, "%d", &num);
			stk->push(stk, num);
		} else { // Operator
			int num1 = stk->pop(stk);
			int num2 = stk->pop(stk);
			switch (token[0]) {
			case '+':
				stk->push(stk, num2 + num1); break;
			case '-':
				stk->push(stk, num2 - num1); break;
			case '*':
				stk->push(stk, num2 * num1); break;
			case '/':
				assert(num1 != 0); //divide by 0
				stk->push(stk, num2 / num1); break;
			}
		}
		token = strtok(NULL, " ");
	}
	return stk->pop(stk);
}

전체 코드

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
#include <string.h>
#include <ctype.h>

struct stack {
	int top;
	int stack_size;
	int *arr;
	bool (*is_empty)(struct stack *);
	void (*push)(struct stack *, int);
	int (*pop)(struct stack *);
};

bool cb_is_empty(struct stack *s)
{
	if (s->top == -1)
		return true;
	return false;
}

void cb_push(struct stack *s, int val)
{
	s->arr[++(s->top)] = val;
}

int cb_pop(struct stack *s)
{
	if (!s->is_empty(s))
		return s->arr[s->top--];
	return -1;
}

struct stack *stack_init(int size)
{
	struct stack *s = (struct stack *)calloc(1, sizeof(struct stack));
	if (s == NULL) return NULL;
	s->top = -1;
	s->stack_size = size;
	s->arr = (int *)calloc(size, sizeof(int));
	if (s->arr == NULL) return NULL;
	s->is_empty = cb_is_empty;
	s->push = cb_push;
	s->pop = cb_pop;
	return s;
}

void unit_test_stack(struct stack *myst)
{
	myst->push(myst, 1);
	myst->push(myst, 2);
	myst->push(myst, 3);
	myst->push(myst, 4);
	myst->push(myst, 5);
	
	for (int i = 5; i > 0; i--)
		assert(myst->pop(myst) == i);
	assert(myst->pop(myst) == -1);
	assert(myst->top == -1);
}


int nr_token(char *exp)
{
	int ret = 0;
	while (*exp != '\0')
		if (*exp++ == ' ')
			ret++;
	return ret + 1;
}

int stack_calculator(struct stack *stk, char *exp)
{
	char *token = strtok(exp, " "); // using strtok() for seperating token from exp

	while (token != NULL) {
		if (isdigit(token[0])) { //NOTE: number token always begin with digit
			int num = 0;
			sscanf(token, "%d", &num);
			stk->push(stk, num);
		} else { // Operator
			int num1 = stk->pop(stk);
			int num2 = stk->pop(stk);
			switch (token[0]) {
			case '+':
				stk->push(stk, num2 + num1); break;
			case '-':
				stk->push(stk, num2 - num1); break;
			case '*':
				stk->push(stk, num2 * num1); break;
			case '/':
				assert(num1 != 0); //divide by 0
				stk->push(stk, num2 / num1); break;
			}
		}
		token = strtok(NULL, " ");
	}
	return stk->pop(stk);
}

#define TEST 0
int main(int argc, char *argv[])
{
#if TEST
	struct stack *myst = stack_init(10);
	unit_test_stack(myst);
	free(myst->arr);
	free(myst);
#endif
	int num_of_tkn = nr_token(argv[1]);
	struct stack *calc_stack = stack_init(num_of_tkn);
	printf("expression: %s\n", argv[1]);
	printf("result: %d\n", stack_calculator(calc_stack, argv[1]));
	free(calc_stack->arr);
	free(calc_stack);

	return 0;
}