CLEAN CODE: EVALUATE EXPRESSION | STACKS | DATA STRUCTURE PROBLEM

By: Saurav

2018-02-07 01:22:00 UTC

Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are +, -, *, /. Each operand may be an integer or another expression.

Examples:

["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6

InterviewBit

Good thing that we already have tests in our problem statement.

The algorithm is all about using LIFO:
If expression if found, take the last two elements from the stack, evaluate and then add result back to the stack
Otherwise, add the element
Finally, print the only element in the stack.

;lets write some tests and then see it in action:

p evalRPM(["2", "1", "+", "3", "*"]) ==  9
p evalRPM(["4", "13", "5", "/", "+"]) == 6

def evalRPN(arr)
  
      return if arr.length < 1 
      stack = Array.new
      top = 0
      
      (0..arr.length - 1).each do |i|
        if arr[i] == "0" or arr[i].to_i > 0 or arr[i].to_i < 0
          stack << arr[i]
        elsif arr[i].to_i == 0
          a = stack.pop.to_i
          b = stack.pop.to_i
          op = arr[i]
          top = eval(a,b,op)
          stack << top
        end 
      end
      
      return stack[0]
    end 
    
    def eval(a,b,op)
      if op == "+"
        return b+a
      elsif op == "-"
        return b-a
      elsif op == "*"
        return b*a
      elsif op == "/"
        return b/a if a!=0 
      end
    end 

Looks good to me.


Let me know what you think!
twitter: sprakash24oct
linkedin

Owned & Maintained by Saurav Prakash

If you like what you see, you can help me cover server costs or buy me a cup of coffee though donation :)