algorithms/leetcode/150-EvaluateReversePolishNotation.go at master · freewu/algorithms · GitHub

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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
package main

// 150. Evaluate Reverse Polish Notation
// 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.

// Example 1:
// Input: tokens = ["2","1","+","3","*"]
// Output: 9
// Explanation: ((2 + 1) * 3) = 9

// Example 2:
// Input: tokens = ["4","13","5","/","+"]
// Output: 6
// Explanation: (4 + (13 / 5)) = 6

// Example 3:
// Input: tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
// Output: 22
// Explanation: ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
// = ((10 * (6 / (12 * -11))) + 17) + 5
// = ((10 * (6 / -132)) + 17) + 5
// = ((10 * 0) + 17) + 5
// = (0 + 17) + 5
// = 17 + 5
// = 22

// Constraints:
//     1 <= tokens.length <= 10^4
//     tokens[i] is either an operator: "+", "-", "*", or "/", or an integer in the range [-200, 200].

import "fmt"
import "strconv"

func evalRPN(tokens []string) int {
    stack := make([]int, 0, len(tokens))
    for _, token := range tokens {
        v, err := strconv.Atoi(token)
        if err == nil { // 如果是数字 能被转换成功 压入栈中
            stack = append(stack, v)
        } else { // 不是数字说明是 符号
            // 取出最顶端的数字
            num1, num2 := stack[len(stack) - 2], stack[len(stack) - 1]
            stack = stack[:len(stack)-2]

            switch token { // 四则运算后,重新入栈
            case "+":
                stack = append(stack, num1 + num2)
            case "-":
                stack = append(stack, num1 - num2)
            case "*":
                stack = append(stack, num1 * num2)
            case "/":
                stack = append(stack, num1 / num2)
            }
        }
    }
    return stack[0]
}

// stack
func evalRPN1(tokens []string) int {
    stack := make([]int, 0)
    // 先判断符号 减少 strconv.Atoi 的调用次数
    for _, token := range tokens {
        if token == "-" {
            left := stack[len(stack) - 2]
            right := stack[len(stack) - 1]
            stack = stack[:len(stack) - 2]
            stack = append(stack, left - right)
        } else if token == "+" {
            left := stack[len(stack) - 2]
            right := stack[len(stack) - 1]
            stack = stack[:len(stack) - 2]
            stack = append(stack, left + right)
        } else if token == "/" {
            left := stack[len(stack) - 2]
            right := stack[len(stack) - 1]
            stack = stack[:len(stack) - 2]
            stack = append(stack, left / right)
        } else if token == "*" {
            left := stack[len(stack) - 2]
            right := stack[len(stack) - 1]
            stack = stack[:len(stack) - 2]
            stack = append(stack, left * right)
        } else {
            val, _ := strconv.Atoi(token)
            stack = append(stack, val)
        }
    }
    return stack[0]
}

func main() {
    // Example 1:
    // Input: tokens = ["2","1","+","3","*"]
    // Output: 9
    // Explanation: ((2 + 1) * 3) = 9
    fmt.Printf("evalRPN([]string{\"2\",\"1\",\"+\",\"3\",\"*\" }) = %v\n",evalRPN([]string{ "2","1","+","3","*" })) // 9  ((2 + 1) * 3)
    // Example 2:
    // Input: tokens = ["4","13","5","/","+"]
    // Output: 6
    // Explanation: (4 + (13 / 5)) = 6
    fmt.Printf("evalRPN([]string{\"4\",\"13\",\"5\",\"/\",\"+\"}) = %v\n",evalRPN([]string{ "4","13","5","/","+" })) // 6 (4 + (13 / 5))
    // Example 3:
    // Input: tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
    // Output: 22
    // Explanation: ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
    // = ((10 * (6 / (12 * -11))) + 17) + 5
    // = ((10 * (6 / -132)) + 17) + 5
    // = ((10 * 0) + 17) + 5
    // = (0 + 17) + 5
    // = 17 + 5
    // = 22
    fmt.Printf("evalRPN([]string{\"10\",\"6\",\"9\",\"3\",\"+\",\"-11\",\"*\",\"/\",\"*\",\"17\",\"+\",\"5\",\"+\"}) = %v\n",evalRPN([]string{ "10","6","9","3","+","-11","*","/","*","17","+","5","+" })) // 22 ((10 * (6 / ((9 + 3) * -11))) + 17) + 5

    fmt.Printf("evalRPN1([]string{\"2\",\"1\",\"+\",\"3\",\"*\" }) = %v\n",evalRPN1([]string{ "2","1","+","3","*" })) // 9  ((2 + 1) * 3)
    fmt.Printf("evalRPN1([]string{\"4\",\"13\",\"5\",\"/\",\"+\"}) = %v\n",evalRPN1([]string{ "4","13","5","/","+" })) // 6 (4 + (13 / 5))
    fmt.Printf("evalRPN1([]string{\"10\",\"6\",\"9\",\"3\",\"+\",\"-11\",\"*\",\"/\",\"*\",\"17\",\"+\",\"5\",\"+\"}) = %v\n",evalRPN1([]string{ "10","6","9","3","+","-11","*","/","*","17","+","5","+" })) // 22 ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
}