前言
愚蠢如我。
正文
问题来源
本问题来自leetcode上的150题。用go语言做的
问题描述
根据逆波兰表示法，求表达式的值。
有效的运算符包括+, -, *, / 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
说明：
整数除法只保留整数部分。 给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。
示例 :
输入: ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]
输出: 22
解释:
((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
分析：
自己写的代码好多地方都没有进行优化，居然没有用栈，现在想想可笑至极。贴出来自勉一下。 本人写的Go代码如下：
func evalRPN(tokens []string) int {
l := len(tokens)
for ; l != 1 ; {
i := 0
for ; i < l-2; i++ {
//居然不知道go语言可以使用字符串进行判断内容是否相同
if ((tokens[i][0]>='0'&&tokens[i][0] <= '9') ||
len(tokens[i])!=1) &&
((tokens[i+1][0]>='0'&&tokens[i+1][0] <= '9') ||
len(tokens[i+1])!=1)&&
((tokens[i+2][0]<'0'||tokens[i+2][0] > '9') &&
len(tokens[i+2]) == 1) {
break;
}
}
a, _ := strconv.Atoi(tokens[i])
b, _ := strconv.Atoi(tokens[i+1])
c := 0
if tokens[i+2][0] == '+' {
c = a + b
} else if tokens[i+2][0] == '-' {
c = a - b
} else if tokens[i+2][0] == '*' {
c = a * b
} else {
c = a / b
}
num := strconv.Itoa(c)
tokens[i] = num
//防止越界
if i == l - 3 {
tokens = tokens[:i+1]
} else {
tokens = append(tokens[:i+1],tokens[i+3:]...)
}
l = len(tokens)
}
a, _ := strconv.Atoi(tokens[0])
return a
}
网上参考代码是使用的栈
func evalRPN(tokens []string) int {
//避免slice扩充重新分配，导致时间开销
nums := make([]int, 0, len(tokens))
for _, s := range tokens {
if s == "+" || s == "-" || s == "*" || s == "/" {
b, a := nums[len(nums) - 1], nums[len(nums) - 2]
//栈弹出
nums = nums[:len(nums) - 2]
nums = append(nums, compute(a, b, s))
} else {
temp, _ := strconv.Atoi(s)
nums = append(nums, temp)
}
}
return nums[0]
}
func compute(a, b int, opt string) int {
switch opt {
case "+" :
return a + b
case "-":
return a - b
case "*" :
return a * b
default:
return a / b
}
}
总结：
勤思考
结语
不管怎么样好好加油。
