栈的应用
一、数制转换：
将十进制整数N转换为r（r<10)进制数，N、r通过键盘输入。
输入：N、r
输出：转换后的数
例如：输入：N=67, r=8
输出：15205
二、逆置输出
将从键盘输入的字符序列逆置输出，回车（换行符）结束输入（也可用其他字符表示输入结束）。例如：
输入：tset a si sihT
输出：This is a test
三、括号匹配：
试编写程序，检查输入的圆括号串的括号是否配对，若配对输出“OK”，若不配对输
出“Error ”。
输入：（（（）（）））
输出： OK
输入：（））（
输出：Error
四、背包问题
问题：假设有n件质量分配为w1，w2，...，wn的物品和一个最多能装载总质量为T的背包，能否从这n件物品中选择若干件物品装入背包，使得被选物品的总质量恰好等于背包所能装载的最大质量，即wi1+wi2+...+wik=T。若能，则背包问题有解，否则无解。
算法思想：首先将n件物品排成一列，依次选取；若装入某件物品后，背包内物品的总质量不超过背包最大装载质量时，则装入（进栈）；否则放弃这件物品的选择，选择下一件物品试探，直至装入的物品总和正好是背包的最大转载质量为止。这时我们称背包装满。
若装入若干物品的背包没有满，而且又无其他物品可以选入背包，说明已装入背包的物品中有不合格者，需从背包中取出最后装入的物品（退栈），然后在未装入的物品中挑选，重复此过程，直至装满背包（有解），或无物品可选（无解）为止。
具体实现：设用数组w[n]，stack[n]分别存放物品重量和已经装入背包（栈）的物品序号，M表示背包的最大装载量。每进栈一个物品，就从M中减去该 物品的质量,设i为
待选物品序号,若M-w[i]>=0，则该物品可选；若M-w[i] < 0，则该物品不可选,且若i>n，则需退栈，若此时栈空，则说明无解。
输入：背包的最大装载量M， 物品数量n，n件物品重量
输出：（有解）列出装入包内的物品重量，有多组解时只要求输出任一组。
（无解）“No answer\"
例如：
输入：M=20, n=5, W[5]=11, 5, 8, 6, 7
输出：5 8 7
输入：M=10, n=5, W[5]=11, 5, 8, 6, 7
输出：No answer
练习：
1、进制转换
我们可以用这样的方式来表示一个十进制数： 将每个阿拉伯数字乘以一个以该数字所处位置的（值减１）为指数，以１０为底数的幂之和的形式。例如：１２３可表示为１＊１０２＋２＊１０１＋３＊１００这样的形式。
与之相似的,对二进制数来说,也可表示成每个二进制数码乘以一个以该数字所处位置的(值-1)为指数,以2为底数的幂之和的形式｡一般说来,任何一个正整 数R或一个负整数-R都可以被选来作为一个数制系统的基数｡如果是以R或-R为基数,则需要用到的数码为0,1,....R-1｡例如,当R=7时,所需 用到的数码是0,1,2,3,4,5和6,这与其是R或-R无关｡如果作为基数的数绝对值超过10,则为了表示这些数码,通常使用英文字母来表示那些大于 9的数码｡例如对16进制数来说,用A表示10,用B表示11,用C表示12,用D表示13,用E表示14,用F表示15｡
在负进制数中是用-R 作为基数,例如-15(十进制)相当于110001(-2进制),并且它可以被表示为2的幂级数的和数:
110001=1*(-2)5+1*(-2)4+0*(-2)3+0*(-2)2+ 0*(-2)1 +1*(-2)0
设计一个程序，读入一个十进制数和一个负进制数的基数, 并将此十进制数转换为此负进制下的数： -R∈{-2,-3,-4,...,-20}
输入：
输入的每行有两个输入数据。
第一个是十进制数Ｎ（－32768＜＝Ｎ＜＝32767）； 第二个是负进制数的基数－Ｒ。
输出：
结果显示在屏幕上，相对于输入，应输出此负进制数及其基数，若此基数超过１０，则参照１６进制的方式处理。
输入
30000 -2
-20000 -2
28800 -16
-25000 -16
输出
30000=11011010101110000(base -2)
-20000=1111011000100000 (base -2)
28000=19180 (base -16)
-25000=7FB8 (base -16)
2、单词统计
读入一英文句子，单词之间用空格或逗号隔开，统计其中单词个数，并输出各个字母出现的频率。(句子末尾不一定用\".\"结束) 如果含有其他的字符，则只要求输出错误信息及错误类型。
含有大写字母 错误类型 error 1
数字（0-9） 错误类型 error 2
其他非法字符 错误类型 error 3
如 输入： It is 12!
输出： error 1 2 3
输入： i am ,a student
输出： 4
3、 编码解码：
从键盘输入一个英文句子，设计一个编码、解码程序。(string)
编码过程：先 键入一个正整数N(1<=N<=26)。这个N决定了转换关系。 例如当N=1，输入的句子为ABCXYZ时，则其转换码为ABCXYZ不变。当N=2时，其转换码为BCDYZA，其它的非字母字符不变。为使编码较于破 译，将转换码的信息自左而右两两交换，若最后仅剩单个字符则不换。然后，将一开始表示转换关系的N根据ascii表序号化成大写字母放在最前面。
如：abcABCxyzXYZ-/,1. n=3
cdeCDEzabZAB-/,1. {根据N的值转换}
dcCeEDazZbBA/-1,. {两两交换}
CdcCeEDazZbBA/-1,. {最后编码}
解码过程为编码的逆过程。
4、计算器的改良【第三届全国青少年信息学奥林匹克分区联赛复赛试题普及组题一】
〖问题描述〗
NCL是一家专门从事计算器改良与升级的实验室。最近该实验室收到了某公司所委托的一个任务：需要在该公司某型号的计算器上加上解一元一次方程的功能。实 验室将这个任务交组了一个刚进入的新手ZL先生。为了很好的完成这个任务，ZL先生首先研究了一些一元一次方程的实例：
4+3X=8
6a-5+1=2-2
-5+12Y=0
ZL先生被告知：在计算器上键入的一个一元一次方程中，只包含整数、小写字母入+、-、=这三个数学符号（当然，“-”既可当减号也可当负号）。方程中并没有括号，也没有除号，方程中的字母表示末知数。
〖问题求解〗
编写程序，解输入的一元一次方程，将解方程的结果（精确到小数点后三位）输出至屏幕。
键入的一元一次方程均合法，且有唯一的实数解。
〖样例〗
输入：6a-5+1=2-2a
输出：a=0.750
5、求封闭区域面积
如下图：求图中被*围成的封闭区域的面积（方格的个数不包括*所在的方格，且*不在最外一层）。
[输入数据]：
第一行： Ｍ Ｎ 表示有Ｍ行Ｎ列
后面Ｍ行 每行Ｎ个数字，０表示空，１表示该位置有*
[输出数据]：
一行： 面积大小
[算法分析]：
用一个二维数组存储这张图，先统计“封闭曲线”外的０的数量，把总个数减去线外的，再减去*的个数就是曲线内的面积。
外围个数的统计方法： 从左上角的第一个‘０’开始找相邻的‘０’，找到后入队，一个0的相邻位置找完后，再找队列中下一个０的相邻位置，一直到队列空为止。
6、魔术师变牌问题
芸芸和楠楠在玩扑克牌，她们共有n张扑克，这些扑克上分别记为1,2，…，n,芸芸打开扑克第一张是1，把它放在一边然后把最上面2张一张一张地依次移到 最后，打开上面一张，刚好是2，放在一边，然后把最上面3张一张一张地依次移到最后，打开上面一张，刚好是3。。。。。。如此继续下去，直至打开最后一张 是n，放在一边，这时楠楠发现，放在一边的扑克刚好是按1,2，3……n这样排列的，好想知道，在开始的时候应当怎样排放这些扑克，才能得到这样的结果， 你能帮她写个程序求出扑克的最先排列顺序吗？
例如：当n=5时，原排列是：1 4 5 2 3;当n=9时，原排列是：1 8 6 2 9 4 5 3 7
〖算法分析一〗
逆推法：按照芸芸做的方式倒着作一遍，就得到了扑克的原始顺序了。从芸芸的玩法中知道，要翻出第i张扑克（也就是扑克i），首先要把最上面的i张牌移到最后，然后最上面的就是扑克i了。所以，我们可以倒过来，先把扑克i放在最上面，然后将最后面的i张牌移到上面。
(1)把n张牌看成是n~1的n个数组成的队列，用数组a存放。
(2)用数组b来表示要求的原排列，首先将n移到b队列，移牌计数器i=n-1。
(3)将a中最大的牌移到队列b中。
(4)在队列b中，从队首移动i个数到队尾，i减1。
(5)重复(3)(4)两步，直到前面n-1张牌拿出了为止。
(6)把最后一张牌1直接放入队列b的队尾，然后将队列b从队尾到队首的顺序输出，就是扑克的最先排列顺序。
〖算法分析二〗
来一个人工模拟方法：在桌子上放13空盒子排成一圈，从1开始顺序编号，将扑克1放入1号盒子中，从下一个空盒子开始对空的盒子计数，当数到第三个空盒 子时，将扑克
2放入空盒子中，然后再从下一个空盒子开始对空盒子计数，扑克i应该放在第i+1个空盒子中，顺序放入3、4、5...，直到放入全部n张 牌。注意在计数时要跳过非空的盒子，只对空盒子计数。最后牌在盒子中的顺序，就是原来牌的顺序。（看明白了吗，是不是有点像约瑟夫问题呢？）
7.自然数拆分
例：自然数的有序拆分。任何一个大于1的自然数总可以拆分成若干个自然数之和。
4＝1＋1＋1＋1
4＝1＋1＋2
4＝1＋3
4＝2＋2
分析：设有序拆分出的数s1≤s2≤…≤sk。定义数组s为一个栈，用来存放因子。从1开始搜索因子，求和，若sum ≤n就将因子压栈；若sum ＝n，则输出解，出栈；若sum ＞n，则修改栈顶元素的值，即回溯。
