1.栈在括号匹配中的应用
#include<iostream>
#include<string>
#define maxSize 10
using namespace std;
//定义顺序栈，采用静态数组
typedef struct sqStack {
string data;
int top;
}sqStack;
//初始化栈
bool initStack(sqStack& S) {
S.top = -1;
return true;
}
//进栈
bool push(sqStack& S, char e) {
if (S.top == maxSize - 1) return false;
S.data[++S.top] = e;
return true;
}
//出栈
bool pop(sqStack& S, char& e) {
if (S.top == -1) return false;
e = S.data[S.top--];
return true;
}
//判断栈空
bool emptyStack(sqStack S) {
if (S.top == -1) return false;
else return true;
}
//括号匹配
bool bracket(string str) {
sqStack S;
initStack(S);
//获得字符串长度
int length = str.length();
//保存栈顶的元素
char topElem;
//遍历字符串
for (int i = 0; i < length; i++) {
//当前是'{'进栈
if (str[i] == '{') push(S, str[i]);
//当前是'}'出栈，进行匹配
else if (str[i] == '}') {
pop (S, topElem);
if (topElem != '{') return false;
}
//当前是'['进栈
else if (str[i] == '[') push(S, str[i]);
//当前是']'出栈，进行匹配
else if (str[i] == ']') {
pop (S, topElem);
if (topElem != '[') return false;
}
//当前是'('进栈
else if (str[i] == '(') push(S, str[i]);
//当前是')'出栈，进行匹配
else if (str[i] == ')') {
pop (S, topElem);
if (topElem != '(') return false;
}
}
//循环结束后，栈空则匹配成功
if (emptyStack) return true;
else return false;
}2.栈在表达式求值中的运用
前缀表达式：运算符在两个操作数前面
+a b //操作数1
* c d //操作数2
- + a b * c d
中缀表达式：运算符在两个操作数中间
a + b - c * d
后缀表达式：运算符在两个操作数后面
a b + //操作数1
c d * //操作数2
a b + c d * -
2.1.中缀表达式转换后缀表达式
- 确定中缀表达式的各个运算符的运算顺序
- 选择下一个运算符，按照【左操作数 右操作数 运算符】的方式组成一个新的操作数（整体）
- 如果还有运算符，则重复2
- "左优先"原则：只要左边的运算符能先计算，则优先计算左边（转换后的后缀表达式不唯一，采用左优先原则可以保证后缀唯一）
中缀表达式：((15 / (7 - (1 + 1))) * 3) - (2 + (1 + 1))
后缀表达式：
(1)1 1 +
(2)7 1 1 + -
(3)15 7 1 1 + - /
(4)3 15 7 1 1 + - / * //左操作数
(5)1 1 +
(6)2 1 1 + +
(7)3 15 7 1 1 + - / * 2 1 1 + + -
2.2.后缀表达式的计算方法
从左往右扫描，每遇到一个运算符，就让运算符前面最近的两个操作数执行对应运算，合并为一个操作数
//括号表示括号内为一个整体操作数
//3 15 7 1 1 + - / * 2 1 1 + + -
(1)1 1 +
(2)7 (1 1 +） -
(3)15 (7 (1 1 +） -) /
(4)3 (15 (7 (1 1 +） -) /) *
(5)1 1 +
(6)2 (1 1 +)
(7)(3 (15 (7 (1 1 +） -) /) *) (2 (1 1 +)) -
//括号表示括号内为一个整体操作数
//A B C D - * + E F / -
(1)C D -
(2)B (C D -) *
(3)A B (C D -) * +
(4)E F /
(5)(A B (C D -) * +) (E F /) -
2.3.中缀表达式转换前缀表达式
- 确定中缀表达式的各个运算符的运算顺序
- 选择下一个运算符，按照【 运算符 左操作数 右操作数】的方式组成一个新的操作数（整体）
- 如果还有运算符，则重复2
- "右优先"原则：只要右边的运算符能先计算，则优先计算右边（转换后的后缀表达式不唯一，采用右优先原则可以保证后缀唯一）
1.中缀表达式：A + B * (C - D) - E / F
前缀表达式：
(1)/ E F
(2)- C D
(3)* B - C D
(4)+ A * B - C D
(5)- + A * B - C D / E F
2.4. 中缀表达式转后缀表达式（机算——栈）
- 初始化一个栈，用于保存暂时还不能确定运算顺序的运算符
- 从左到右依次处理各个元素。有三种情况
a.遇到操作数。直接加入到后缀表达式
b.遇到界限符。遇到"("直接入栈；遇到")"依次弹出站内运算符并且假如后缀表达式，直到弹出"("为止。注意："("不加入后缀表达式
c.遇到运算符。依次弹出栈中优先级高于或等于当前运算符的所有运算符，并加入后缀表达式。若碰到"("或栈空则停止。之后再把当前运算符入栈
3.按照上述方法处理完所有字符后，依次弹出栈中剩余运算符，并假如后缀表达式中
A + B - C * D / E + F
(1)
扫描到'A'：'A'是操作数，直接加入后缀表达式
后缀表达式：A
栈：空
(2)
扫描到'+'：'+'是运算符，此时栈空，入栈
后缀表达式：A
栈：+
(3)
扫描到'B'：'B'是操作数，直接加入后缀表达式
后缀表达式：A B
栈：+
(4)
扫描到'-'：'-'是运算符，因为栈顶元素为'+'，与'-'同优先级，因此，弹出'+'加入后缀表达式后，将'-'入栈
后缀表达式：A B +
栈：-
(5)
扫描到'C'：'C'是操作数，直接加入后缀表达式
后缀表达式：A B + C
栈：-
(6)
扫描到'*'：'*'是运算符，因为栈顶元素为'-'，优先级＜'*'，因此，将'*'入栈
后缀表达式：A B + C
栈：- *
(7)
扫描到'D'：'D'是操作数，直接加入后缀表达式
后缀表达式：A B + C D
栈：- *
(8)
扫描到'/'：'/'是运算符，因为栈顶元素为'*'，与'/'同优先级 && 优先级＞'-'，因此，弹出'*'加入后缀表达式后，将'/'入栈
后缀表达式：A B + C D *
栈：- /
(9)
扫描到'E'：'E'是操作数，直接加入后缀表达式
后缀表达式：A B + C D * E
栈：- /
(10)
扫描到'+'：'+'是运算符，因为栈顶元素为'/'，优先级＜'/' && 优先级 = '-'，因此，依次弹出'/''-'加入后缀表达式后，将'+'入栈
后缀表达式：A B + C D * E / -
栈：+
(11)
扫描到'F'：'F'是操作数，直接加入后缀表达式
后缀表达式：A B + C D * E / - F
栈：+
(12)
所有符号全部扫描完毕，清空栈中元素，并使其加入后缀表达式中
后缀表达式：A B + C D * E / - F +
栈：空
A + B * (C - D) - E / F
(1)
扫描到'A'：'A'是操作数，直接加入后缀表达式
后缀表达式：A
栈：空
(2)
扫描到'+'：'+'是运算符，此时栈空，入栈
后缀表达式：A
栈：+
(3)
扫描到'B'：'B'是操作数，直接加入后缀表达式
后缀表达式：A B
栈：+
(4)
扫描到'*'：'*'是运算符，栈中元素'+' < '*'，'*'入栈
后缀表达式：A B
栈：+ *
(5)
扫描到'('：'('是界限符，入栈
后缀表达式：A B
栈：+ * (
(6)
扫描到'C'：'C'是操作数，直接加入后缀表达式
后缀表达式：A B C
栈：+ * (
(7)
扫描到'-'：'-'是运算符，此时栈顶元素为'('，入栈
后缀表达式：A B C
栈：+ * ( -
(8)
扫描到'D'：'D'是操作数，直接加入后缀表达式
后缀表达式：A B C D
栈：+ * ( -
(9)
扫描到')'：')'是界限符，出栈直到出栈元素为'('，加入出栈元素中的运算符
后缀表达式：A B C D -
栈：+ *
(10)
扫描到'-'：'-'是运算符，优先级＜'*' && 优先级 = '+'，依次出栈，并将'-'入栈
后缀表达式：A B C D - * +
栈：-
(11)
扫描到'E'：'E'是操作数，直接加入后缀表达式
后缀表达式：A B C D - * + E
栈：-
(12)
扫描到'/'：'/'是运算符，优先级＞'-'，入栈
后缀表达式：A B C D - * + E
栈：- /
(13)
扫描到'F'：'F'是操作数，直接加入后缀表达式
后缀表达式：A B C D - * + E F
栈：- /
(14)
扫描完所有字符，依次弹出栈中元素，并将其加入后缀表达式中
后缀表达式：A B C D - * + E F / -
栈：空2.5.中缀表达式的计算（机算）
用栈实现：
- 初始化两个栈，操作数栈和运算符栈
- 若扫描到操作数，压入操作数栈
- 若扫描到运算符或界限符，则按照“中缀转后缀”相同的逻辑压入运算符栈（期间也会弹出运算符，每当弹出一个运算符时，就需要再弹出两个操作数栈的栈顶元素并执行相应运算，运算结果再压回操作数栈）
A + B - C * D / E + F
(1)
扫描到'A'：进操作数栈
操作数栈：A
运算符栈：空
(2)
扫描到'+'：运算符栈空，因此，进入运算符栈
操作数栈：A
运算符栈：+
(3)
扫描到'B'：进入操作数栈
操作数栈：A B
运算符栈：+
(4)
扫描到'-'：运算符栈顶元素为'+'，优先级相等，因此，弹出'+'和操作数栈的两个元素计算，计算结果压回操作数栈，后'-'进运算符栈
操作数栈：(A B +)
运算符栈：-
(5)
扫描到'C'：进入操作数栈
操作数栈：(A B +) C
运算符栈：-
(6)
扫描到'*'：运算符栈顶元素为'-'，优先级＜'*'，因此，'*'进栈
操作数栈：(A B +) C
运算符栈：- *
(7)
扫描到'D'：进入操作数栈
操作数栈：(A B +) C D
运算符栈：- *
(8)
扫描到'/'：运算符栈顶元素为'*'，优先级相等，因此，弹出'*'和操作数栈的两个元素计算，计算结果压回操作数栈，后'/'进运算符栈
操作数栈：(A B +) (C D *)
运算符栈：- /
(9)
扫描到'E'：进入操作数栈
操作数栈：(A B +) (C D *) E
运算符栈：- /
(10)
扫描到'+'：运算符栈中优先级都>='+'，因此依次弹出，并将计算结果压入操作数栈中，后将'+'入运算符栈
操作数栈：(A B + C D * E / -)
运算符栈：+
(11)
扫描到'F'：进入操作数栈
操作数栈：(A B + C D * E / -) F
运算符栈：+
(12)
扫描完全部字符，弹出运算符栈中所有元素，并计算
A B + C D * E / - F +
