> For the complete documentation index, see [llms.txt](https://leetcodebook-1.gitbook.io/top-interview-150/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://leetcodebook-1.gitbook.io/top-interview-150/stack/evaluate-reverse-polish-notation.md).

# 逆波兰表达式求值

题目链接: <https://leetcode.cn/problems/evaluate-reverse-polish-notation>

## 解题思路：

1. 遍历tokens，判断是否是算符，是则从栈顶出栈两个元素进行计算
2. 否则，转换成int，入栈

```go
func evalRPN(tokens []string) int {
	queue := make([]int, 0)
	for _, item := range tokens {
		last := len(queue) - 1
		switch item {
		case "+":
			val1, val2 := queue[last], queue[last-1]
			queue = append(queue[:last-1], val2+val1)
		case "-":
			val1, val2 := queue[last], queue[last-1]
			queue = append(queue[:last-1], val2-val1)
		case "*":
			val1, val2 := queue[last], queue[last-1]
			queue = append(queue[:last-1], val2*val1)
		case "/":
			val1, val2 := queue[last], queue[last-1]
			queue = append(queue[:last-1], val2/val1)
		default:
			data, _ := strconv.Atoi(item)
			queue = append(queue, data)
		}
	}
	return queue[0]
}
```

## 复杂度分析

* **时间复杂度：** 只遍历了一遍tokens，因此时间复杂度为 $$O(n)$$，其中 $$n$$ 是字符串数组 `tokens` 的长度
* **空间复杂度：** 只使用了一个栈，因此空间复杂度为 $$O(n)$$，