題目

給定一個逆波蘭式，計算這個逆波蘭式的值。

解析

對于一個 rp，其計算方式為，從后往前將字符壓棧，如果棧頂兩個都是數(shù)字，則拿出一個符號和三個數(shù)字進行計算，計算結(jié)果扔回棧里，其他情況均壓棧。如此往復(fù)，直到棧底出現(xiàn)一個數(shù)字。

偽代碼

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 是符號時，從棧中拿出兩個數(shù)字計算，結(jié)果扔回棧里
3. 遍歷完成后結(jié)果在棧上

偽代碼

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