﻿---
layout:     post
title:      leetcode150逆波兰表达式求值
subtitle:   leetcode150Evaluate Reverse Polish Notation
date:       2018-08-22
author:     BY
header-img: img/post-bg-universe.jpg
catalog: true
tags:
    - Blog
---


## 前言

愚蠢如我。

## 正文

### 问题来源

本问题来自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
    }
}
```
#### 总结：
勤思考

## 结语
不管怎么样好好加油。