150. Evaluate Reverse Polish Notation

Problem¶

You are 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 be any division by zero.
• The input represents a valid arithmetic expression in a reverse polish notation.
• The answer and all the intermediate calculations can be represented in a 32-bit integer.

Solve¶

White board¶

A fancy name, in my academy year, we call it Postfix expression.

We used stack to storing the calculated number data:

• If we process a number token, add it to the stack
• If we process a operator token, pop 2 top of the stack number, do the operation on them and push result back to the stack
• After all calculation, the stack should have only one element.

A invalid mathematics formula is found when we either:

• Not have enough number in stack to do a operation
• Having more than one element in the stack after all calculation

Implement¶

c
O(n)

Not even draft code first with python like what i usually do, I think it better to have some practice with c to solve this problem.

First, we handle a string token instead of direct number, or operator:

• This mean we wan’t to separating which is which, thus I need to implementing isOperator to check:
  • A token string with length isn’t equal to 1 is not a operator
  • If they is, the only character should be +, -, * or /
• If we found a number as string, we want to handle by process it back to integer for easier calculation. We dealing with the number range of [-200, 200], so we need to handle the - sign for negative number

I process without (almost) no data validating at all here because I assuming that all input of the problem is always a valid

or else their will be specifically say what I should return when it have invalid result

After that is implementing Post-fix expression formula calculation, which involve implementing a Stack:

• Here I can use an array implementation of stack for quick coding time. With default size of \(10^4\) , with 3 basic function pop, push, init
• Formula calculation process implementation, which is just exactly what we said in white board session. Pop and push immediate calculation result over stack until we process all of provided Post-fix formula tokens.
• The final result is the only element left in the stack after all calculation

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

int isOperation(char *str) {
  if (strlen(str) != 1) {
    return 0;
  }

  int c = str[0];
  return c == '+' || c == '-' || c == '*' || c == '/';
}

int getNumber(char *str) {
  int num = 0;
  int sign = 1;
  for (int i = 0; i < strlen(str); i++) {
    int c = str[i];
    if (c == '-') {
      sign = -1;
      continue;
    }
    num *= 10;
    num += c - '0';
  }

  return num * sign;
}

typedef struct {
  int value[10000];
  int top;
} Stack;

int pop(Stack *s) {
  int res = s->value[s->top];
  s->top--;
  return res;
}

void push(Stack *s, int value) {
  s->top++;
  s->value[s->top] = value;
}

void init(Stack *s) { s->top = -1; }

int evalRPN(char **tokens, int tokensSize) {
  int result = 0;
  char *curr = 0;
  Stack stack;
  int expr1, expr2;

  init(&stack);

  for (int i = 0; i < tokensSize; i++) {
    curr = tokens[i];
    if (!isOperation(curr)) {
      push(&stack, getNumber(curr));
    } else {
      expr2 = pop(&stack);
      expr1 = pop(&stack);
      switch (curr[0]) {
      case '+': {
        push(&stack, expr1 + expr2);
        break;
      }
      case '-': {
        push(&stack, expr1 - expr2);
        break;
      }
      case '*': {
        push(&stack, expr1 * expr2);
        break;
      }
      case '/': {
        // int default to trunc toward zero
        push(&stack, expr1 / expr2);
        break;
      }
      default: {
        printf("Found invalid operator %s", curr);
      }
      }
    }
  }

  result = stack.value[0];
  if (stack.top != 0) {
    printf("Invalid formula!!");
  }

  return result;
}

int main() {
  int res = 0;
  char *s[5];
  // tokens = ["2","1","+","3","*"]

  s[0] = "2";
  s[1] = "1";
  s[2] = "+";
  s[3] = "3";
  s[4] = "*";
  res = evalRPN(s, 5);
  printf("%d\n", res);

  char *s2[13] = {"10","6","9","3","+","-11","*","/","*","17","+","5","+"};
  res = evalRPN(s2, 13);
  printf("%d\n", res);
}

After thought¶

At first, when trying to solve this problem, My first thought is that I can’t gain anything back from the problem. This already been solve by me in Mathematic expression calculation. While playing with python, i can easily use most of build-in function to speedup the process

But, using c to re-write it again, it interesting to see some thing like this line

char *s2[13] = {"10","6","9","3","+","-11","*","/","*","17","+","5","+"};

I’m amazed that how little validate I done in this implementation, normally when dealing with math, the validating take a ton of time to get thing right, even meaning

Also without much practice, it’s easy to forget how to write switch case (for a time limited code session, I would rather using if statement all the way tbh)

int main() {
  int res = 0;
  char *s[5];
  // tokens = ["2","1","+","3","*"]

  s[0] = "2";
  s[1] = "1";
  s[2] = "+";
  s[3] = "3";
  s[4] = "*";
  res = evalRPN(s, 5);
  printf("%d\n", res);

  char *s2[13] = {"10","6","9","3","+","-11","*","/","*","17","+","5","+"};
  res = evalRPN(s2, 13);
  printf("%d\n", res);
}