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 +
