Leetcode - 150. Evaluate Reverse Polish Notation

문제

후위 표기법으로 수식을 계산하기.

Input: tokens = ["2","1","+","3","*"]
Output: 9
Explanation: ((2 + 1) * 3) = 9

https://leetcode.com/problems/evaluate-reverse-polish-notation/

이전에 구현했던 구현 방법 그대로 사용 가능 -> 후위 표기법 스택 계산기

해결 O(N)

#include <ctype.h>

struct stack {
    int top;
    int ssize;
    int *arr;
    void (*push)(struct stack *, int);    
    int (*pop)(struct stack *);    
};

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

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

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

int evalRPN(char ** tokens, int tokensSize){
    struct stack *st = stack_init(tokensSize);
    for (int i = 0; i < tokensSize; i++) {
        if (isdigit(tokens[i][0])
            || (tokens[i][0] == '-' && isdigit(tokens[i][1]))) {
            int num = 0;
            sscanf(tokens[i], "%d", &num);
            st->push(st, num);
        } else {
            int num1 = st->pop(st);
            int num2 = st->pop(st);
            switch(tokens[i][0]) {
                case '+': st->push(st, num2 + num1); break;
                case '-': st->push(st, num2 - num1); break;
                case '*': st->push(st, num2 * num1); break;
                case '/': st->push(st, num2 / num1); break;
            }
        }
    }
    return st->pop(st);
}