150. Evaluate Reverse Polish Not

题目

给定一个逆波兰式，计算这个逆波兰式的值。

解析

对于一个 rp，其计算方式为，从后往前将字符压栈，如果栈顶两个都是数字，则拿出一个符号和三个数字进行计算，计算结果扔回栈里，其他情况均压栈。如此往复，直到栈底出现一个数字。

伪代码

stack
for {
  if stack[bottom] is  num
    return num
  if stack[top] & stack[top-1] is num
     num = calc(stack[top] , stack[top-2], stack[top-1])
     stack[top-2] = num
     continue
  stack[top+1] = tokens[i]
}

代码

const (
    ADD = 201
    SUB = 202
    MUL = 203
    DIV = 204
)

func evalRPN(tokens []string) int {
    stack := make([]int, len(tokens))
    top:=0
    
    i := len(tokens)-1
    for {
        if top > 0 && isNum(stack[0]) {
            return stack[0]
        }
        if top > 2 && isNum(stack[top-1]) && isNum(stack[top-2]) {
            stack[top-3] = calc(stack[top-3], stack[top-1], stack[top-2])
            top-=2
            continue
        }
        if i >= 0 {
            val, _ := parseToken(tokens[i])
            stack[top] = val
            i--
            top++
        }
    }
    return 0
    
}

func isNum(token int) bool {
    switch {
    case token>=ADD && token <= DIV:
        return false
    default:
        return true
    }
}

func atoi(s string) int {
    i:=0
    var isNeg bool
    if s[i] == '-' {
        isNeg = true
        i++
    }
    num := 0
    for ;i<len(s); i++ {
        num = num * 10 + int(s[i] - '0')
    }
    if isNeg {
        num = ^num + 1
    }
    return num
}

func calc(op, a, b int) int {
    switch op {
    case ADD:
        return a+b
    case SUB:
        return a-b
    case MUL:
        return a*b
    case DIV:
        return a/b
    }
    return 0
}

func parseToken(s string) (val int, isNum bool) {
    switch s {
    case "+":
      return 201, false
    case "-":
      return 202, false
    case "*":
      return 203, false
    case "/":
      return 204, false
    default:
        return atoi(s), true
    }
}

逆波兰式的正确计算方法

1. 顺序压栈
2. 当 token 是符号时，从栈中拿出两个数字计算，结果扔回栈里
3. 遍历完成后结果在栈上

伪代码

for token in toknes
  if isOp(token)
    stack[top-2] = calc(op, stack[top-2]. stack[top-1])
    top--
 else
    stack[top] = token
    top++

 return stack[0]

代码

const (
    ADD = 201
    SUB = 202
    MUL = 203
    DIV = 204
)

func evalRPN(tokens []string) int {
    stack := make([]int, len(tokens))
    top:=0

    for i := range tokens {
      val, is := parseToken(tokens[i])
      if is {
        stack[top] = val
        top++
      }else {
        stack[top-2] = calc(val, stack[top-2], stack[top-1])
        top--
      }
    }
    return stack[0]
}

func atoi(s string) int {
    i:=0
    var isNeg bool
    if s[i] == '-' {
        isNeg = true
        i++
    }
    num := 0
    for ;i<len(s); i++ {
        num = num * 10 + int(s[i] - '0')
    }
    if isNeg {
        num = ^num + 1
    }
    return num
}

func calc(op, a, b int) int {
    switch op {
    case ADD:
        return a+b
    case SUB:
        return a-b
    case MUL:
        return a*b
    case DIV:
        return a/b
    }
    return 0
}

func parseToken(s string) (val int, isNum bool) {
    switch s {
    case "+":
      return 201, false
    case "-":
      return 202, false
    case "*":
      return 203, false
    case "/":
      return 204, false
    default:
        return atoi(s), true
    }
}

image.png