1、左右括号匹配
2、汉诺塔
3、车厢编序
4、电子布线
5、离线等价类
6、迷宫
(1)括号匹配问题
首先读入字符串将每个括号按序保存在字符数组中
依次判断每个字符，如果是开放字符则压入栈中
如果是关闭字符而且此时栈为空的话，那么字符串非平衡串，栈不为空且栈顶的开放字符与关闭字符相匹配的话，则弹出栈顶，否则非平衡串。
在字符数组结尾处，如果栈非空则非平衡串，反之则是。
这个比较容易实现，就不实现了。
//测试用例
char a[] = "(())abc{[(])}" ; // 左右括号次序匹配不正确
char b[] = "(()))abc{[]}" ; // 右括号多于左括号
char c[] = "(()()abc{[]}" ; // 左括号多于右括号
char d[] = "(())abc{[]()}" ; // 左右括号匹配正确
(2)十进制表示N进制
十进制表示N进制的话，将十进制对N取余的结果保存在栈中，按序输出栈即可。
while (true) {
// 将余数入栈
myStack.push(result % n);
result = result / n;
if (result == 0) {
break;
}
}
(3)行编辑
输入行中字符‘#’表示退格’@’表示前面的输入无效
public static String lineEdit(String input){
Stack<Character> myStack = new ArrayStack<Character>();
char[] arr = input.toCharArray();
for (char c : arr) {
if (c == '#') {
myStack.pop();
} else if (c == '@') {
myStack.clear();
} else {
myStack.push(c);
}
}
return myStack.toString();
}
(2)逆波兰表达式(后缀表达式)
什么是逆波兰表达式？
通常我们计算一个算式：X+Y,(操作数X，操作符+，操作数Y)；逆波兰表达式是(操作数X,操作数Y，操作符+)；
在后缀表达式中看，不存在括号，也不存在运算符优先级的差别，计算过程完全按照运算符出现的先后次序进行，整个计算过程仅需扫描一遍便可完成。
中缀表达式转后缀表达式
如上图所示的，将左边的转换成右边的。
为了转换正确，必须设定一个运算符栈，并在栈底放入一个特殊算符，假定为@，让它具有最低的运算符优先级，此栈用来保存扫描中缀表达式得到的暂不能放入后缀表达式中的运算符，待它的两个运算对象都放入到后缀表达式之后，再令其出栈并写入到后缀表达式中。
转换过程如下：从头到尾扫描中缀表达式，
(1)若遇到数字则直接写入后缀表达式，
(2)若遇到运算符，则比较栈顶元素和该运算符的优先级,
(2.1)(* 或者/ )当该运算符的优先级大于栈顶元素的时候，表明该运算符的后一个运算对象还没有进入后缀表达式，应该把该运算符暂存于运算符栈中，然后把它的后一个运算对象写入到后缀表达式中，再令其出栈并写入后缀表达式中；(比如说*和/)
(2.2)(- 或者+)若遇到的运算符优先级小于等于栈顶元素的优先级，表明栈顶运算符的两个运算对象已经被写入后缀表达式，应将栈顶元素出栈并写入后缀表达式，对于新的栈顶元素仍进行比较和处理，直到栈顶元素为#，然后将新元素进栈。
string InToLast(string& str)
{
stack<char> op;//符号
string res;//结果
op.push('#');
for (size_t i = 0; i < str.size(); ++i)
{
if (isalnum(str[i]))
res += str[i];
else//符号
{
if (str[i] == '(')
op.push(str[i]);
else if (str[i] == ')')
{
char tmp = op.top();
while (tmp != '(')
{
op.pop();
res += tmp;
tmp = op.top();
}
op.pop();
}
else if (str[i] == '+' || str[i] == '-')
{
char tmp = op.top();
if (tmp == '('|| tmp == '#')
op.push(str[i]);
else
{
while (op.size() > 1)
{
res += tmp;
op.pop();
tmp = op.top();
}
op.push(str[i]);
}
}
else if (str[i] == '*' || str[i] == '/')
{
op.push(str[i]);
}
}
}
while (op.size() > 1)
{
res += op.top();
op.pop();
}
return res;
}
后缀表达式求值
后缀表达式求值也需要一个栈，其元素类型为操作数的类型，此栈存储后缀表达式中的操作数、计算过程的中间结果及最后结果。
