【栈和队列】leetcode150——逆波兰表达式求值

作者:神秘网友 发布时间:2021-02-27 10:50:32

【栈和队列】leetcode150——逆波兰表达式求值

编号150: 逆波兰表达式求值

根据逆波兰表示法,求表达式的值。

有效的运算符包括 + , -, * , / 。每个运算对象可以是整数,也可以是另一个逆波兰表达式。

说明:

整数除法只保留整数部分。给定逆波兰表达式总是有效的。换句话说,表达式总会得出有效数值且不存在除数为 0 的情况。

示例 1:
输入: ["2", "1", "+", "3", " * "]
输出: 9
解释: 该算式转化为常见的中缀算术表达式为:((2 + 1) * 3) = 9
示例 2:
输入: ["4", "13", "5", "/", "+"]
输出: 6
解释: 该算式转化为常见的中缀算术表达式为:(4 + (13 / 5)) = 6
示例 3:
输入: ["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

逆波兰表达式:是一种后缀表达式,所谓后缀就是指算符写在后面。

平常使用的算式则是一种中缀表达式,如 ( 1 + 2 ) * ( 3 + 4 ) 。

该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。

思路

前述:

逆波兰表达式主要有以下两个优点:

  • 去掉括号后表达式无歧义,上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。
  • 适合用栈操作运算:遇到数字则入栈;遇到算符则取出栈顶两个数字进行计算,并将结果压入栈中。

「其实逆波兰表达式相当于是二叉树中的后序遍历」。大家可以把运算符作为中间节点,按照后序遍历的规则画出一个二叉树。例如:对于4 13 5 / +这个逆波兰表达式,对于的二叉树如下所示:

可以安装二叉树的后续遍历,得到该逆波兰表达式。

求解过程:

遍历逆波兰表达式,遇到数字进栈,当遇到数学运算符时,将栈里的前两个元素pop出栈再与运算符运算,得到的数再入栈。

具体代码如下:

//遍历逆波兰表达式,遇到数字进栈,当遇到数学运算符时,
//将栈里的前两个元素分别出栈再与运算符运算,得到的数再入栈。
func evalRPN(tokens []string) int {
	stack := make([]int, 0)

	for i := 0; i  len(tokens); i++ {
		if tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/" {
			//将栈顶前两个元素出栈
			num1 := stack[len(stack)-1]  //获取栈顶元素
			stack = stack[:len(stack)-1] //pop出栈 更新栈
			num2 := stack[len(stack)-1]
			stack = stack[:len(stack)-1]

			//判断各个运算符 进行对应得运算操作后再push进栈
			if tokens[i] == "+" {
				stack = append(stack, num2+num1) //注意运算顺序
			}
			if tokens[i] == "-" {
				stack = append(stack, num2-num1)
			}
			if tokens[i] == "*" {
				stack = append(stack, num2*num1)
			}
			if tokens[i] == "/" {
				stack = append(stack, num2/num1)
			}
		} else { //说明遇到得时数字  string - int入栈
			num, _ := strconv.Atoi(tokens[i])
			stack = append(stack, num)
		}
	}
	result := stack[len(stack)-1]
	return result
}

【栈和队列】leetcode150——逆波兰表达式求值 相关文章

  1. 阻塞队列

    概念 阻塞队列(BlockingQueue):支持2个 附加操作 的队列。阻塞队列常用于生产者和消费者的场景, 生产者 是往队列中添加元素的线程, 消费者 是从队列中获取元素的线程。 附加操作 : 1)队列为空时,获取元素的线程会等待队列变为非空 2)队列为满时,存

  2. 牛牛与交换排序 题解(双端队列模拟区间反转)

    题目链接 题目大意 给你一个长度为n的全排列 你固定一个区间翻转长度k,你每次可以做任意次数的翻转 但是一旦某一次操作选择了数组的某个位置进行区间翻转操作,下一次做区间翻转的位置将会比上一次 更靠右。 要你判断是否能让数组变成升序,满足则输出k 题

  3. 【栈和队列】leetcode20——有效的括号

    编号20:有效的括号 给定一个只包括 '(',')','{','}','[',']' 的字符串,判断字符串是否有效。 有效字符串需满足: 左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 注意空字符串可被认为是有效字符串。 示例 1:输入: "()"输出: true

  4. Java创建栈和队列的几种方式

    1.创建队列 1.1 使用Queue接口 ,Queue的实现类有LinkedList和PriorityQueue。最常用的实现类是LinkedList。 Queue的六种方法: add()和 offer() 向队列中添加元素,将元素压入队尾。当超出容量时add()会抛出异常 , offer()会返回false。 remove()

  5. Dyno-queues 分布式延迟队列 之 辅助功能

    Dyno-queues 分布式延迟队列 之 辅助功能 目录 Dyno-queues 分布式延迟队列 之 辅助功能 0x00 摘要 0x01 前文回顾 0x2 Ack机制 2.1 加入Un-ack集合 2.2 ACK 2.3 处理Un-ACK的消息 2.3.1 定时任务 2.3.2 Un-ACK 0x03 防止重复消费 0x04 防止消息丢失 4.1 消息

  6. 2020 BIT冬训-图DFSBFS B - Rescue HDU - 1242(BFS,优先队列)

    Problem DescriptionAngel was caught by the MOLIGPY! He was put in prison by Moligpy. The prison is described as a N * M (N, M = 200) matrix. There are WALLs, ROADs, and GUARDs in the prison. Angel's friends want to save Angel. Their task is

  7. 字节跳动面试官这样问消息队列:高可用、不重复消费、可靠传输、顺序消费、消息堆积,我整理了下

    写在前面 又到了年底跳槽高峰季,很多小伙伴出去面试时,不少面试官都会问到消息队列的问题,不少小伙伴回答的不是很完美,有些小伙伴是心里知道答案,嘴上却没有很好的表达出来,究其根本原因,还是对相关的知识点理解的不够透彻。今天,我们就一起来探讨下

  8. RabbitMQ——安装、集群搭建、镜像队列配置

    一、环境说明 1、Centos7.7-64位 2、Erlang-OTP 23 3、RabbitMQ-3.8.9 操作系统 ip 主机名 配置 centos 7.7 17.16.10.62 rabbit-1 4核8g centos 7.7 17.16.10.63 rabbit-2 4核8g centos 7.7 17.16.10.66 rabbit-3 4核8g 二、下载安装文件 1、RabbitMQ软件:

  9. QTAILQ队列数据结构

    QTAILQ队列数据结构 这种数据结构由两种基本结构构成,分别是QTAILQ_ENTRY和QTAILQ_HEAD,前者表示队列的元素,后者表示队列的头。 #define QTAILQ_ENTRY(type) \union { \ struct type *tqe_next; /* next element */ \ QTailQLink tqe_circ; /* link for c

  10. 【栈和队列】leetcode232——用栈实现队列

    编号232: 用栈实现队列 请你仅使用两个栈实现先入先出队列。队列应当支持一般队列的支持的所有操作( push 、 pop 、 peek 、 empty ): push(x) -- 将一个元素放入队列的尾部。 pop() -- 从队列首部移除元素。 peek() -- 返回队列首部的元素。 empty() --

每天更新java,php,javaScript,go,python,nodejs,vue,android,mysql等相关技术教程,教程由网友分享而来,欢迎大家分享IT技术教程到本站,帮助自己同时也帮助他人!

Copyright 2020, All Rights Reserved. Powered by 跳墙网(www.tqwba.com)|网站地图|关键词