讯享网

 <p id="34KTR12K">专栏：50多种数据结构彻底征服</p><p id="34KTR12L">专栏：50多种经典图论算法全部掌握</p><p id="34KTR12N">这段时间，上海青浦华为练秋湖研发中心第一批3000名研发人员已经入驻，预计明年春节前后，大约25000人进驻办公，明年年底，完成约30000人。</p><p id="34KTR12P">华为青浦研发中心也为应届生提供了公寓，公寓有华为智慧屏，松下洗衣机，智能马桶，华为门锁，可以入住两年。从公寓关门到公司打卡五分钟不到的路程，这在上海普遍一个小时的上班时间来说已经非常非常近了。</p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F1029%2Fe375ac05j00sm3iae0038d200hb0098g00hb0098.jpg&thumbnail=660x&quality=80&type=jpg"/><br/></p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F1029%2Fe1b71b57j00sm3iaf005fd200u001hcg00u001hc.jpg&thumbnail=660x&quality=80&type=jpg"/><br/></p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F1029%2Fa8018bb5j00sm3iaf001pd200u000mig00u000mi.jpg&thumbnail=660x&quality=80&type=jpg"/><br/></p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F1029%2F8ab0b7afj00sm3iag001ld200u000mig00u000mi.jpg&thumbnail=660x&quality=80&type=jpg"/><br/></p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F1029%2F8da843d7j00sm3iag003ad200u000mig00u000mi.jpg&thumbnail=660x&quality=80&type=jpg"/><br/></p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F1029%2F92c88943j00sm3iah002ad200u000mig00u000mi.jpg&thumbnail=660x&quality=80&type=jpg"/><br/></p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F1029%2Fca993ccaj00sm3iai002vd200cn00pcg00cn00pc.jpg&thumbnail=660x&quality=80&type=jpg"/><br/></p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F1029%2F99dc1a83j00sm3iaj002cd200cn00kzg00cn00kz.jpg&thumbnail=660x&quality=80&type=jpg"/><br/></p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F1029%2Fdf571aa6j00sm3iak002md200cn00prg00cn00pr.jpg&thumbnail=660x&quality=80&type=jpg"/><br/></p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F1029%2Ff2a3442aj00sm3iak001sd200cn00jvg00cn00jv.jpg&thumbnail=660x&quality=80&type=jpg"/><br/></p><p id="34KTR13K">--------------下面是今天的算法题--------------</p><p id="34KTR13M">来看下今天的算法题，这题是LeetCode的第150题：逆波兰表达式求值。</p><p id="34KTR13Q">问题描述</p><p id="34KTR141">来源：LeetCode第150题<br/></p><p id="34KTR142">难度：中等</p><p id="34KTR146">给你一个字符串数组 tokens ，表示一个根据逆波兰表示法表示的算术表达式。请你计算该表达式。返回一个表示表达式值的整数。</p><p id="34KTR148">示例1：<br/></p><p><br/><blockquote id="34KTR15K">输入：tokens = ["2","1","+","3","*"] 输出：9 解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9</blockquote><br/></p><p id="34KTR149">示例2：<br/></p><p><br/><blockquote id="34KTR15L">输入：tokens = ["4","13","5","/","+"] 输出：6 解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6</blockquote><br/></p><p><ul><li id="34KTR15I"></p><p id="34KTR14B">1 &lt;= tokens.length &lt;= 10^4</p><p></li><li id="34KTR15J"></p><p id="34KTR14C">tokens[i] 是一个算符（"+"、"-"、"*" 或 "/"），或是在范围 [-200, 200] 内的一个整数</p><p></li></ul></p><p id="34KTR14G">问题分析</p><p id="34KTR14N">我们平时书写的表达式是中缀表达式，运算符在中间，操作数在两边，比如a+b。逆波兰表达式也就是 后缀表达式 ，操作数在前，运算符在后，比如 a b + 。还有一个是前缀表达式，是波兰表达式，运算符在前，操作数在后，比如 + a b 。</p><p id="34KTR14P">对于我们人来说中缀表达式是最容易计算的，但对于计算机来说更容易计算的是前缀表达式和后缀表达式。关于前，中，后三种表达式的相互转换有堆栈法，二叉树法和括号法，具体可以看下 《 中的第十三章。<br/></p><p id="34KTR14R">对于逆波兰表达式的计算我们只需要使用一个栈即可，遍历字符串数组，如果遇到数字就入栈，如果是运算符就从栈中弹出两个数字， 注意先出栈的是右值，后出栈的是左值 ，把它们计算的结果入栈，直到字符串数组遍历完为止。<br/></p><p id="34KTR14T">JAVA：</p><pre></pre></p><p id="34KTR151">C++：</p><pre></pre><br/></p><p id="34KTR153">Python：</p><pre></pre><br/></p><p id="34KTR159"><strong>笔者简介</strong></p><p id="34KTR15A">博哥，真名：<strong>王一博</strong>，毕业十多年， 作者，专注于 数据结构和算法 的讲解，在全球30多个算法网站中累计做题2000多道，在公众号中写算法题解800多题，对算法题有自己独特的解题思路和解题技巧，喜欢的可以给个关注，也可以 下载我整理的1000多页的PDF算法文档 。</p>