https://github.com/Lanying0/lintcode
所属:
数据结构->线性结构->栈
问题:
给定一个表达式字符串数组,返回该表达式的逆波兰表达式(即去掉括号)。
样例
对于 [3 - 4 + 5]的表达式(该表达式可表示为["3", "-", "4", "+", "5"]),返回 [3 4 - 5 +](该表达式可表示为 ["3", "4", "-", "5", "+"])。
思路:
逆波兰的一般思路,对于输入的字符串,构建两个栈,一个栈中暂存运算符号,另一个栈中存表达式结果。
从头到尾一遍扫描字符串:遇到运算数,则直接压入表达式结果栈;遇到运算符,则要根据运算符优先级分情况处理。
运算符情况:1.左括号:直接压入符号栈。
2.加号、减号,优先级最低,所以要将栈中的加减乘除号先出栈到表达式结果栈,再将加减号入栈。
3.乘号、除号,优先级最高,所以只需将栈中的乘除号出栈到表达式结果栈,再将此次的乘除号入栈。
4.右括号:将栈中左括号之后入栈的运算符全部出栈到表达式结果栈,左括号出栈。
一遍扫描后,若符号栈不为空,则将其全部出栈到表达式结果栈。即为所求。
代码:
class Solution {
public:
/**
* @param expression: A string array
* @return: The Reverse Polish notation of this expression
*/
vector<string> convertToRPN(vector<string> &expression) {
// write your code here
vector<string>op;//符号栈
vector<string>num;//表达式结果栈
for(int i=0;i<expression.size();i++)//一遍扫描
{
if(expression[i]=="+" || expression[i]=="-")//处理加号、减号
{
if(op.size()==0)
op.push_back(expression[i]);
else
{
while(op.size()!=0 && (op[op.size()-1]=="*" || op[op.size()-1]=="/" ||op[op.size()-1]=="+" || op[op.size()-1]=="-"))
{
string s=op.back();
op.pop_back();
num.push_back(s); } op.push_back(expression[i]);
}
if(op[op.size()-1]=="(")
{
op.push_back(expression[i]);
}
}
else if(expression[i]=="*" || expression[i]=="/")//处理乘号、除号
{
if(op.size()==0)
op.push_back(expression[i]);
else if(op[op.size()-1]=="*" || op[op.size()-1]=="/" )
{
string s=op.back();
op.pop_back();
num.push_back(s);
op.push_back(expression[i]);
}
else if(op[op.size()-1]=="+" || op[op.size()-1]=="-")
{
op.push_back(expression[i]);
}
else if(op[op.size()-1]=="(")
{
op.push_back(expression[i]);
}
}
else if(expression[i]=="(")//处理左括号
{
op.push_back(expression[i]);
}
else if(expression[i]==")")//处理右括号
{
while(op.back()!="(")
{
string s=op.back();
op.pop_back();
num.push_back(s);
}
op.pop_back();
}
else//运算数直接压入表达式结果栈
{
num.push_back(expression[i]);
}
}
while(op.size()!=0)//符号栈仍有符号时,将其压入表达式结果栈
{
string s=op.back();
op.pop_back();
num.push_back(s);
}
return num;
}
};
c++实现将表达式转换为逆波兰表达式的更多相关文章
-
shunting-yard 调度场算法、中缀表达式转逆波兰表达式
中缀表达式 1*(2+3) 这就是一个中缀表达式,运算符在数字之间,计算机处理前缀表达式和后缀表达式比较容易,但处理中缀表达式却不太容易,因此,我们需要使用shunting-yard Algorith ...
-
SDIBT2666——逆波兰表达式求值
逆波兰表达式求值(栈和队列) Description 从键盘上输入一个逆波兰表达式,用伪码写出其求值程序.规定:逆波兰表达式的长度不超过一行,以@符作为输入结束,操作数之间用空格分隔,操作符只可能有+ ...
-
JavaScript实现计算后缀表达式(逆波兰表达式)以及将中缀表达式转为后缀表达式
逆波兰表达式,它的语法规定,表达式必须以逆波兰表达式的方式给出.逆波兰表达式又叫做后缀表达式.这个知识点在数据结构和编译原理这两门课程中都有介绍,下面是一些例子: 正常的表达式 逆波兰表达式 a+b ...
-
noi1696 逆波兰表达式
1696:逆波兰表达式 http://noi.openjudge.cn/ch0303/1696/ 总时间限制: 1000ms 内存限制: 65536kB 描述 逆波兰表达式是一种把运算符前置的算术 ...
-
150. Evaluate Reverse Polish Notation逆波兰表达式
[抄题]: Evaluate the value of an arithmetic expression in Reverse Polish Notation. Valid operators are ...
-
C#数据结构与算法系列(十):逆波兰计算器——逆波兰表达式(后缀表达式)
1.介绍 后缀表达式又称逆波兰表达式,与前缀表达式相似,只是运算符位于操作数之后 2.举例说明 (3+4)*5-6对应的后缀表达式就是3 4 +5 * 6 - 3.示例 输入一个逆波兰表达式(后缀表达 ...
-
【python】Leetcode每日一题-逆波兰表达式求值
[python]Leetcode每日一题-逆波兰表达式求值 [题目描述] 根据 逆波兰表示法,求表达式的值. 有效的算符包括 +.-.*./ .每个运算对象可以是整数,也可以是另一个逆波兰表达式. 说 ...
-
AC日记——逆波兰表达式 openjudge 3.3 1696
1696:逆波兰表达式 总时间限制: 1000ms 内存限制: 65536kB 描述 逆波兰表达式是一种把运算符前置的算术表达式,例如普通的表达式2 + 3的逆波兰表示法为+ 2 3.逆波兰表达式 ...
-
OpenJudge 2694 逆波兰表达式
1.链接地址: http://bailian.openjudge.cn/practice/2694/ 2.题目: 总时间限制: 1000ms 内存限制: 65536kB 描述 逆波兰表达式是一种把运算 ...
随机推荐
-
SQL Server 2008 R2中,“选择前1000行”为“选择所有行”
从SQL Server 2008开始,微软为了提高查询效率等原因,右键点击表时弹出菜单中默认没有"显示所有行",而以"选择前1000行"替代. 点击[工具]-& ...
-
Java学习笔记之:Java的变量
一.介绍 在Java语言中,所有的变量在使用前必须声明.声明变量的基本格式如下: type identifier [ = value][, identifier [= value] ...] ; 格式 ...
-
实例源码--Android高德地图实例源码
下载源码 技术要点: 1.高德地图 API的使用 2.定位 ,查询路线,公交查询等地图相关技术 3.源码带有非常详 细的中文注释 ...... 详细介绍: 1. 高德地图API的使用 本套实例采 ...
-
Struts2方法调用的三种方式
在Struts2中方法调用概括起来主要有三种形式 第一种方式:指定method属性 <action name="student" class="com.itmyho ...
-
【淡墨Unity3D Shader计划】四 热带雨林的文章: 排除、深度测试、Alpha测试和基本雾编译
本系列文章由@浅墨_毛星云 出品,转载请注明出处. 文章链接:http://hpw123.net/a/C__/kongzhitaichengxu/2014/1222/163.html 作者:毛星云 ...
-
http协议的补充二
一,浏览器到服务器request 1.1,浏览器里面的内容 请求(浏览器->服务器) GET /day09/hello HTTP/1.1 Host: localhost:8080 User-Ag ...
-
python进程池
当需要创建的子进程数量不多时,可以直接利用multiprocessing中的Process动态成生多个进程,但如果是上百甚至上千个目标,手动的去创建进程的工作量巨大,此时就可以用到multiproce ...
-
Linux Nginx Web环境安装SSL证书后强行指向HTTPS方法
如今我们越来越多的网站需要使用SSL证书,尤其是一些购物类网站,用户交互类网站使用居多.安装方法也很简单,我们可以根据自己的服务器是NGINX还是APACHE进行安装,但是在安装之后,默认的HTTP和 ...
-
hdu2973 YAPTCHA【威尔逊定理】
<题目链接> 题目大意: The task that is presented to anyone visiting the start page of the math departme ...
-
如何避免Scrum敏捷开发团队反思会形式化,海星法介绍
如何避免Scrum敏捷开发团队反思会形式化? 迭代压力很大,根本没时间,而且,反思会上大家都在互相推脱责任,会议成了“*大会”,所以团队的人都觉得这个会很鸡肋. 很多团队在开反思会时是这么干的:产品 ...