棧在括號匹配中的應用

流程圖

代碼

#include <stdio.h>
#include <stdlib.h>
#define MaxSize 10typedef struct {char data[MaxSize];int top;
} SqStack;// 初始化棧
void InitStack(SqStack* S) {S->top = -1; // 初始化棧頂指針
}// 判空
bool StackEmpty(SqStack* S) {if (S->top == -1) {return true;} else {return false;}
}// 入棧
bool Push(SqStack* S, char x) {if (S->top == MaxSize - 1) { // 棧滿，報錯return false;} else {S->top = S->top + 1; // 指針先加1S->data[S->top] = x; // 新元素入棧return true;}
}// 出棧
bool Pop(SqStack* S, char* x) {if (StackEmpty(S)) {return false;} else {*x = S->data[S->top]; // 棧頂元素先出棧S->top = S->top - 1; // 指針減1return true;}
}// 括號匹配檢查
bool bracketCheck(char str[], int length) {SqStack S;InitStack(&S); // 初始化一個棧for (int i = 0; i < length; i++) {if (str[i] == '(' || str[i] == '[' || str[i] == '{') {Push(&S, str[i]); // 掃描到左括號，入棧} else {if (StackEmpty(&S)) { // 掃描到右括號，且當前棧空return false; // 匹配失敗}char topElem;Pop(&S, &topElem); // 棧頂元素出棧if (str[i] == ')' && topElem != '(') {return false;}if (str[i] == ']' && topElem != '[') {return false;}if (str[i] == '}' && topElem != '{') {return false;}}}return StackEmpty(&S); // 檢索全部括號后，棧空說明匹配成功
}int main() {char str[] = "{([()])}";int length = sizeof(str) / sizeof(str[0]) - 1; // 計算字符串長度，減1是為了去掉結尾的'\0'if (bracketCheck(str, length)) {printf("括號匹配成功\n");} else {printf("括號匹配失敗\n");}return 0;
}

棧在表達式求值中的應用

中綴、后綴、前綴表達式

中綴表達式

運算符在兩個操作數中間：

1. a + b
2. a + b - c
3. a + b - c * d

后綴表達式

運算符在兩個操作數后面：

1. ab +
2. ab + c-或者a bc - +
3. ab + cd * -

前綴表達式

運算符在兩個操作數前面：

1. + ab
2. - + ab c
3. - + ab * cd

中綴表達式轉后綴表達式(手算)

1. 確定中綴表達式中各個運算符的運算順序
2. 選擇下一個運算符，按照[左操作數 右操作數 運算符]的方式組合成一個新的操作數（若運算順序不唯一，則后綴表達式也不唯一）
3. 如果還有運算符沒被處理，就繼續2步驟

例：

轉換成后綴表式:? ? ? ? ? 15?7 11+ - / 3 *? 2 11 + + -

"左優先"原則：只要左邊的運算符能先計算，就優先計算左邊的（可保證運算唯一）

后綴表達式的計算(手算)

從左往右掃描，每遇到一個運算符，就讓運算符前面最近的兩個操作數執行對應運算，合體為一個操作數

注意：兩個操作數的左右順序

后綴表達式的計算(機算)

用棧實現后綴表達式的計算：

1. 從左往右掃描下一個元素，直到處理完所以元素
2. 若掃描到操作數則壓入棧，并回到1；否則執行3
3. 若掃描到運算符，則彈出兩個棧頂元素，執行相應運算，運算結果壓回棧頂,回到1

注意：后綴表達式先彈出的元素是‘右操作數’

入棧流程：

?中綴表達式轉前綴表達式(手算)

1. 確定中綴表達式中各個運算符的運算順序
2. 確定下一個運算符，按照[運算符 左操作數 右操作數]的方式組合成一個新的操作數
3. 如果還有運算符沒被處理，就繼續2

"右優先"原則:只要右邊的運算符能先計算，就優先算右邊的

前綴表達式的計算

1. 從右往左掃描下一個元素，直到處理完所有元素
2. 若掃描到操作數則壓入棧，并回到1；否則執行3
3. 若掃描到運算符，則彈出兩個棧頂元素，執行相應運算，運算結構壓回棧頂，回到1

注意前綴表達式先彈出的元素是‘左操作數’

總結