aboutsummaryrefslogtreecommitdiff
path: root/eval_reverse_polish_notation.c
blob: c15c100c0655189124c582b069cc964d84fcc65d (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
// 150. Evaluate Reverse Polish Notation
#include "leetcode.h"

/*
 * given an array of strings 'tokens' that represents an arithmetic expression
 * in a reverse polish notation. evaluate the expression. return an integer that
 * represents the value of the expression. note that the valid operators are + -
 * * and /. each operand may be an integer or another expression. the division
 * between two integers always truncates toward zero. there will not any
 * division by zero. the input represents a valid arithmetic expression in
 * reverse polish notation. the answer and all intermediate calculations can be
 * represented in a 32 bit integer.
 */

int char_to_int(char *s) {
  int len = strlen(s), res = 0;
  bool pos = 1;
  for (int i = 0; i < len; i++) {
    if (s[i] == '-') {
      pos = 0;
      continue;
    }
    res *= 10 + s[i] - '0';
  }
  if (!pos)
    res *= -1;
  return res;
}

int evalRPN(char **tokens, int tokens_size) {
  long long *stack = (long long *)malloc(tokens_size * sizeof(long long));
  int idx = -1;
  long long a, b;
  for (int i = 0; i < tokens_size; i++) {
    if (tokens[i][0] == '+') {
      a = stack[idx];
      idx--;
      b = stack[idx];
      stack[idx] = b + a;
    } else if (strlen(tokens[i]) == 1 && tokens[i][0] == '-') {
      a = stack[idx];
      idx--;
      b = stack[idx];
      stack[idx] = b - a;
    } else if (tokens[i][0] == '*') {
      a = stack[idx];
      idx--;
      b = stack[idx];
      stack[idx] = b * a;
    } else if (tokens[i][0] == '/') {
      a = stack[idx];
      idx--;
      b = stack[idx];
      stack[idx] = b / a;
    } else {
      idx++;
      stack[idx] = char_to_int(tokens[i]);
    }
  }
  int ans = stack[0];
  free(stack);
  return ans;
}

int main() {
  char t1[5][1] = {"2", "1", "+", "3", "*"};
  char t2[5][2] = {"4", "13", "5", "/", "+"};
  char t3[13][3] = {"10", "6", "9",  "3", "+", "-11", "*",
                    "/",  "*", "17", "+", "5", "+"};
  printf("%d\n", evalRPN(t1, 5));  // expect: 9
  printf("%d\n", evalRPN(t2, 5));  // expect: 6
  printf("%d\n", evalRPN(t3, 13)); // expect: 22
}