应用

合法括号序列

用于判断一个包含 ()、{} 等成对括号的序列是否合法。

合法的括号序列，直观上就是左右括号能匹配上。形式化可以定义为：

• 空字符串是合法序列；
• 若 s 是合法序列，则 (s)、{s} 等在两边添加括号的序列也是合法序列；
• 若 a 和 b 是合法序列，则两者的拼接 ab 也是合法序列。

判断方法：遇到左括号时入栈，遇到右括号时，判断是否和左括号相匹配。

特别情况：循环结束后 stk 不为空时，说明有左括号找不到匹配，返回 false；循环过程中遇到右括号，但栈为空，说明有右括号找不到匹配，也返回 false。为了减少循环栈空的特判，可以令栈的第一个元素为特殊字符。

bool is_valid(string s) {
	stack<char> stk;
	stk.push('\0');
	for (char ch: s)
	{
		if (ch == '(' || ch == '[' || ch == '{')
		{
			stk.push(ch);
		}
		else
		{
			if ((ch == ')' && stk.top() == '(') || \
				(ch == ']' && stk.top() == '[') || \
				(ch == '}' && stk.top() == '{'))
			{
				stk.pop();
			}
			else
			{
				return false;
			}
		}
	}
	return stk.size() == 1;
}

表达式求值

用栈可以求一个前缀表达式（波兰表达式，Polish Notation）或者后缀表达式（逆波兰表达式，Reverse Polish Notation）的值。

后缀表达式求值

使用一个栈 stk 存储当前的操作数。顺序遍历，遇到操作数则压栈，遇到运算符则取出栈顶的两个操作数，计算，再将结果压入栈中。

后缀表达式建立表达式树

类似求值，使用一个栈 stk 存储当前的节点。顺序遍历，遇到操作数则建立新节点，遇到运算符则取出栈顶的两个操作数，计算，再将结果压入栈中。

中缀表达式转后缀表达式

这一算法也被称为调度场算法（shunting yard algorithm）