[C] 후위 표기법으로 변환하기

https://leetcode.com/problems/basic-calculator/

이문제에 대한 답인데, 음수의 경우가 아니면 해결된다. ("-2+ 1" 는 풀질 못함)

후위 표기 변환법은 이 알고리즘을 참고

• https://ko.wikipedia.org/wiki/%EC%B0%A8%EB%9F%89%EA%B8%B0%EC%A7%80_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

• https://rudruddl.tistory.com/118

#define UNIT_TEST   0

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

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

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

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

void test_stack(struct stack *s)
{
    s->push(s, 1);
    s->push(s, 3);
    s->push(s, 5);
    s->push(s, 7);
    assert(s->pop(s) == 7);
    assert(s->pop(s) == 5);
    assert(s->pop(s) == 3);
    assert(s->pop(s) == 1);
    assert(s->pop(s) == -1);
    assert(s->top == -1);
    
    s->push(s, '+');
    s->push(s, '-');
    assert(s->pop(s) == '-');
    assert(s->pop(s) == '+');
}

int opt_prio(char c)
{
    switch (c) {
        case '+': return 1;
        case '-': return 1;
        case '*': return 2;
        case '/': return 2;
        //case '(': return 3;
        //case ')': return 3;
    }
    return -1;
}

char *convert_post_exp(char *s, struct stack *stk)
{
    int ssize = strlen(s);
    char *post_exp = (char *)calloc(ssize * 2, sizeof(char));
    int pcnt = 0;
    char ch;
    
    for (int i = 0; i < ssize; i++) {
        switch (s[i]) {
            case '+':
                while (opt_prio(s[i]) <= opt_prio(stk->peek(stk))) {
                    post_exp[pcnt++] = ' ';
                    post_exp[pcnt++] = stk->pop(stk);
                }
                post_exp[pcnt++] = ' ';
                stk->push(stk, '+');
                break;
            case '-':
                while (opt_prio(s[i]) <= opt_prio(stk->peek(stk))) {
                    post_exp[pcnt++] = ' ';
                    post_exp[pcnt++] = stk->pop(stk);
                }
                post_exp[pcnt++] = ' ';
                stk->push(stk, '-');
                break;
            case '(':
                stk->push(stk, '(');
                break;
            case ')':
                while ((ch = stk->pop(stk)) != '(') {
                    post_exp[pcnt++] = ' ';
                    post_exp[pcnt++] = ch;
                }
                break;
            case ' ':
                break;
            default:
                post_exp[pcnt++] = s[i];
                break;
        }
    }
    while (stk->top != -1) {
        post_exp[pcnt++] = ' ';
        post_exp[pcnt++] = stk->pop(stk);
    }
    post_exp[pcnt] = '\0';
    return post_exp;
}

void test_convert_post_exp(struct stack *stk)
{
    char *post_exp = NULL;
    
    post_exp = convert_post_exp("12+1", stk);
    assert(strcmp(post_exp, "12 1 +") == 0);
    free(post_exp);
    post_exp = convert_post_exp("12 +1", stk);
    assert(strcmp(post_exp, "12 1 +") == 0);
    free(post_exp);
    post_exp = convert_post_exp("12+ 1", stk);
    assert(strcmp(post_exp, "12 1 +") == 0);
    free(post_exp);
    post_exp = convert_post_exp("12 + 1", stk);
    assert(strcmp(post_exp, "12 1 +") == 0);
    free(post_exp);
    post_exp = convert_post_exp(" 12+1 ", stk);
    assert(strcmp(post_exp, "12 1 +") == 0);
    free(post_exp);
    post_exp = convert_post_exp(" 12+1", stk);
    assert(strcmp(post_exp, "12 1 +") == 0);
    free(post_exp);
    post_exp = convert_post_exp("12+1 ", stk);
    assert(strcmp(post_exp, "12 1 +") == 0);
    free(post_exp);
    post_exp = convert_post_exp("2 + (20 - 5)", stk);
    assert(strcmp(post_exp, "2 20 5 - +") == 0);
    free(post_exp);
    post_exp = convert_post_exp("(99 + (2 + 20) - 5) - 7", stk);
    assert(strcmp(post_exp, "99 2 20 + + 5 - 7 -") == 0);
    free(post_exp);    
    post_exp = convert_post_exp(" 2-1 + 2 ", stk);
    assert(strcmp(post_exp, "2 1 - 2 +") == 0);
    free(post_exp);    
    post_exp = convert_post_exp("2147483647", stk);
    assert(strcmp(post_exp, "2147483647") == 0);
    free(post_exp);    
}

int calc_post_exp(char *s, struct stack *stk)
{
    char *token = strtok(s, " ");
    while (token != NULL) {
        if (isdigit(token[0])) {
            int val = 0;
            sscanf(token, "%d", &val);
            stk->push(stk, val);
        } else {
            int val1 = stk->pop(stk);
            int val2 = stk->pop(stk);
            switch (token[0]) {
                case '+': stk->push(stk, val2 + val1); break;
                case '-': stk->push(stk, val2 - val1); break;
            };
        }
        token = strtok(NULL, " "); 
    }
    return stk->pop(stk);
}

void test_calc_post_exp(struct stack *stk)
{
    int val;
    char *test_str = (char *)calloc(30, sizeof(char));
    strcpy(test_str, "2 3 +");
    val = calc_post_exp(test_str, stk);
    assert(val == 5);
    
    strcpy(test_str, "12 34 - 50 +");
    val = calc_post_exp(test_str, stk);
    assert(val == 28);
    
    strcpy(test_str, "2147483647");
    val = calc_post_exp(test_str, stk);
    assert(val == 2147483647);
    
    free(test_str);
}

int calculate(char * s){
    int ret = 0;
    char *post_exp = NULL;
    int ssize = strlen(s);
    struct stack *stk = stack_init(ssize);
    
#if UNIT_TEST 
    test_stack(stk);
    test_convert_post_exp(stk);
    test_calc_post_exp(stk);
    printf("Unit Test Result: All Passed\n");
#endif
    post_exp = convert_post_exp(s, stk);
    ret = calc_post_exp(post_exp, stk);
    free(post_exp);
    return ret;
}