野生前端的数据结构练习(1)——栈

大史不说话 发表于 2018/10/10 13:12:56 2018/10/10
【摘要】 习题主要选自Orelly出版的《数据结构与算法javascript描述》一书。参考代码可见:https://github.com/dashnowords/blogs/tree/master/Structure/Stack基本练习根据栈的特性实现一个Stack类,并在后续题目中需要用栈时使用它。编写一个函数unitTrans(num, unit),num为一个10进制数字,unit要转换的进制...

野生前端.jpg

习题主要选自Orelly出版的《数据结构与算法javascript描述》一书。

参考代码可见:https://github.com/dashnowords/blogs/tree/master/Structure/Stack

基本练习

  1. 根据栈的特性实现一个Stack类,并在后续题目中需要用栈时使用它。

  2. 编写一个函数unitTrans(num, unit),num为一个10进制数字,unit要转换的进制数,求转换结果。

  3. 编写一个函数recursion(num),num为一个10进制数字,要求输出num!的结果。

  4. 编写一个函数palindrome(str),str是一个字符串,如果它是一个回文字符串,则返回true,否则返回false

课后习题(书中第四节习题)

  1. 一个算数表达式中有{},(),[]三种括号,编写一个函数,接受一个算数表达式作为参数,如果括号完全匹配则返回true,否则返回括号缺失的位置。

  2. 一个表达式的后缀表达式形式为opt1 opt2 operator,编写一个函数,接受一个算数表达式作为参数(平时使用的算数表达式形式即为中缀表达式),将其转换为后缀表达式(可暂不考虑运算优先级)。

  3. 盒子里从上到下放有不定数量的【红色】,【白色】,【×××】三种糖果,编写一个程序,可以使用一个或多个栈,在保证原糖果顺序不变的情况下,取出所有的【×××】糖果。

习题思路

  1. 按字符逐个解析表达式,遇到左括号即将其压入栈中,遇到右括号就从栈顶弹出一个元素,查看两者是否匹配,若匹配则继续,若不匹配则返回位置。需要注意的是,如果所有括号均配,则栈的最终状态需要为空。

  2. 逆向解析原表达式,将操作数操作符分别压入两个栈中,接着先从操作数栈中弹出第一个元素,在轮流从操作数栈和操作符栈中弹出元素直至栈为空即可。如果从前到后解析,则栈顶的是最后的元素,出栈时考虑到顺序即可。

  3. 只用一个额外的栈即可,将【红色】【白色】糖果压入新栈,将×××糖果移除,当糖果盒为空后,再从新的糖果栈中逐个弹出元素重新放回糖果盒的栈即可。


【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区),文章链接,文章作者等基本信息,否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件至:cloudbbs@huaweicloud.com进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容。
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。