Lintcode370 Convert Expression to Reverse Polish Notation solution 题解
发布在刷题能手——Lintcode 题解2018年3月9日view:227
在文章任何区域双击击即可给文章添加【评注】!浮到评注点上可以查看详情。

【题目描述】

Given an expression string array, return the Reverse Polish notation of this expression. (remove the parentheses)

给定一个表达式字符串数组,返回该表达式的逆波兰表达式(即去掉括号)。

【题目链接】

www.lintcode.com/en/problem/convert-expression-to-reverse-polish-notation/

【题目解析】

转换过程需要用到栈,具体过程如下:

1)如果遇到操作数,我们就直接将其输出。

2)如果遇到操作符,则我们将其放入到栈中,遇到左括号时我们也将其放入栈中。

3)如果遇到一个右括号,则将栈元素弹出,将弹出的操作符输出直到遇到左括号为止。注意,左括号只弹出并不输出。

4)如果遇到任何其他的操作符,如(“+”, “*”,“(”)等,从栈中弹出元素直到遇到发现更低优先级的元素(或者栈为空)为止。弹出完这些元素后,才将遇到的操作符压入到栈中。有一点需要注意,只有在遇到” ) ”的情况下我们才弹出” ( ”,其他情况我们都不会弹出” ( ”。

5)如果我们读到了输入的末尾,则将栈中所有元素依次弹出。

【参考答案】

www.jiuzhang.com/solutions/convert-expression-to-reverse-polish-notation/

评论
发表评论
暂无评论
WRITTEN BY
PUBLISHED IN
刷题能手——Lintcode 题解

日常更新算法刷题~

我的收藏