目錄

0? 引言

1? 棧在括號(hào)匹配中的應(yīng)用

2? 棧在表達(dá)式求值中的應(yīng)用

? ? ? ? 2.1 算數(shù)表達(dá)式

? ? ? ? 2.2 中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式

2.3 后綴表達(dá)式求值

3? 棧在遞歸中的應(yīng)用

3.1 棧在函數(shù)調(diào)用中的作用

3.2 棧在函數(shù)調(diào)用中的工作原理

4? 總結(jié)

---

0? 引言

????????棧（Stack）是一種非常基本且重要的數(shù)據(jù)結(jié)構(gòu)，它們?cè)谠S多計(jì)算機(jī)科學(xué)和軟件工程的應(yīng)用中都有廣泛的用途。

? ? ? ? 棧：

????????????????①括號(hào)匹配；

? ? ? ? ? ? ? ? ②表達(dá)式求值；

? ? ? ? ? ? ? ? ③遞歸函數(shù)調(diào)用。

1? 棧在括號(hào)匹配中的應(yīng)用

? ? ? ? 表達(dá)式中有兩種括號(hào)：圓括號(hào) ( ) 和 方括號(hào) [ ]，嵌套的順序任意，但應(yīng)為正確的格式。

????????例如：( ( [ ]?[ ] ) ) 為正確格式。

? ? ? ? 但如何用算法實(shí)現(xiàn)括號(hào)匹配問(wèn)題？

? ? ? ? 思路如下：

? ? ? ? （1）初始一個(gè)空棧；

? ? ? ? （2）順序讀入括號(hào)；

? ? ? ? （3）當(dāng)讀入的為左括號(hào)，將繼續(xù)讀入括號(hào)，直到讀入第一個(gè)右括號(hào)。那將檢測(cè)與之最近的左括號(hào)是否與之相匹配，若匹配，則出棧；若不匹配，則退出程序。當(dāng)程序結(jié)束時(shí)，棧為空。反之，則表明括號(hào)序列的格式不正確。

? ? ? ? 代碼如下：

#include <stdio.h>  
#include <stdlib.h>  
#include <stdbool.h>  #define MAX_SIZE 100 // 假設(shè)棧的最大大小  typedef struct {  char data[MAX_SIZE];  int top;  
} Stack;  // 初始化棧  
void initStack(Stack *s) {  s->top = -1;  
}  // 判斷棧是否為空  
bool isEmpty(Stack *s) {  return s->top == -1;  
}  // 入棧  
void push(Stack *s, char c) {  if (s->top >= MAX_SIZE - 1) {  printf("Stack overflow\n");  return;  }  s->data[++s->top] = c;  
}  // 出棧  
char pop(Stack *s) {  if (isEmpty(s)) {  printf("Stack underflow\n");  return '#'; // 返回一個(gè)無(wú)效字符，或可以選擇拋出一個(gè)錯(cuò)誤  }  return s->data[s->top--];  
}  // 檢查兩個(gè)括號(hào)是否匹配  
bool isMatch(char c1, char c2) {  if (c1 == '(' && c2 == ')') return true;  if (c1 == '[' && c2 == ']') return true;  if (c1 == '{' && c2 == '}') return true;  return false;  
}  // 括號(hào)匹配函數(shù)  
bool isBalanced(char *str) {  Stack s;  initStack(&s);  for (int i = 0; str[i] != '\0'; i++) {  if (str[i] == '(' || str[i] == '[' || str[i] == '{') {  push(&s, str[i]);  } else if (str[i] == ')' || str[i] == ']' || str[i] == '}') {  if (isEmpty(&s)) {  // 棧為空，但遇到了右括號(hào)，不匹配  return false;  }  char topChar = pop(&s);  if (!isMatch(topChar, str[i])) {  // 棧頂元素與當(dāng)前右括號(hào)不匹配  return false;  }  }  }  // 如果棧為空，則所有括號(hào)都匹配  return isEmpty(&s);  
}  int main() {  char str[MAX_SIZE];  printf("Enter a string with brackets: ");  scanf("%s", str); if (isBalanced(str)) {  printf("The brackets are balanced.\n");  } else {  printf("The brackets are not balanced.\n");  }  return 0;  
}

2? 棧在表達(dá)式求值中的應(yīng)用

? ? ? ? 2.1 算數(shù)表達(dá)式

????????中綴表達(dá)式是人們常用的算術(shù)表達(dá)式，即操作符以中綴形式處于操作數(shù)之間。但在計(jì)算機(jī)中，中綴表達(dá)式相較于前綴和后綴表達(dá)式來(lái)說(shuō)，更不易被計(jì)算機(jī)識(shí)別。前綴表達(dá)式成為波蘭式，后綴表達(dá)式又稱(chēng)逆波蘭式。

? ? ? ? 2.2 中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式

? ? ? ? （1）手算方法：

? ? ? ? ①根據(jù)運(yùn)算順序?qū)Ρ磉_(dá)式運(yùn)算符排號(hào)；

? ? ? ? ②根據(jù)運(yùn)算符排號(hào)順序，將運(yùn)算符及兩端的操作數(shù)以（左操作數(shù) 右操作數(shù) 運(yùn)算符）的順序重新組合。

? ? ? ? 例如：( A + B ) * C + ( D - E ) / F 轉(zhuǎn)后綴表達(dá)式的過(guò)程如下：

? ? ? ??（2）算法實(shí)現(xiàn)：

? ? ? ? ①初始一個(gè)棧；

? ? ? ? ②遇到操作數(shù)，直接加入后綴表達(dá)式；

? ? ? ? ③遇到界限符，若為左括號(hào)直接入棧，若為右括號(hào)，則依次彈出棧中的運(yùn)算符，加入后綴表達(dá)式，知道彈出左括號(hào)為止。需要注意的是，左括號(hào)和右括號(hào)直接刪除，不加入后綴表達(dá)式。

? ? ? ? ④遇到運(yùn)算符，則看運(yùn)算符的優(yōu)先級(jí)，若高于除左括號(hào)外的棧頂元素，則直接入棧。反之，則依次彈出棧中優(yōu)先級(jí)高于或等于當(dāng)前運(yùn)算符的所有運(yùn)算符，并加入后綴表達(dá)式，直到遇到低于他的優(yōu)先級(jí)的運(yùn)算符，才入棧。

#include <stdio.h>  
#include <stdlib.h>  
#include <string.h>  
#include <stdbool.h>  #define MAX_SIZE 100  typedef struct {  char data[MAX_SIZE];  int top;  
} Stack;  // 初始化棧  
void initStack(Stack *s) {  s->top = -1;  
}  // 判斷棧是否為空  
bool isEmpty(Stack *s) {  return s->top == -1;  
}  // 入棧  
bool push(Stack *s, char c) {  if (s->top >= MAX_SIZE - 1) {  return false; // 棧溢出  }  s->data[++s->top] = c;  return true;  
}  // 出棧  
char pop(Stack *s) {  if (isEmpty(s)) {  return '\0'; // ?？?#xff0c;返回空字符  }  return s->data[s->top--];  
}  // 獲取棧頂元素，但不彈出  
char peek(Stack *s) {  if (isEmpty(s)) {  return '\0'; // ?？?#xff0c;返回空字符  }  return s->data[s->top];  
}  // 運(yùn)算符的優(yōu)先級(jí)比較（這里只處理了基本的四則運(yùn)算）  
int precedence(char op) {  if (op == '+' || op == '-') {  return 1;  }  if (op == '*' || op == '/') {  return 2;  }  return 0; // 如果不是運(yùn)算符，返回0  
}  // 將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式  
void infixToPostfix(char *infix, char *postfix) {  Stack s;  initStack(&s);  int i = 0, j = 0;  while (infix[i] != '\0') {  if (infix[i] >= '0' && infix[i] <= '9') {  // 如果是操作數(shù)，直接添加到后綴表達(dá)式中  postfix[j++] = infix[i++];  postfix[j++] = ' '; // 假設(shè)操作數(shù)都是個(gè)位數(shù)，用空格分隔  } else if (infix[i] == '(') {  // 如果是左括號(hào)，直接入棧  push(&s, infix[i++]);  } else if (infix[i] == ')') {  // 如果是右括號(hào)，則彈出棧中元素直到遇到左括號(hào)  while (!isEmpty(&s) && peek(&s) != '(') {  postfix[j++] = pop(&s);  postfix[j++] = ' ';  }  // 彈出左括號(hào)，但不加入后綴表達(dá)式  pop(&s);  i++;  } else {  // 如果是運(yùn)算符  while (!isEmpty(&s) && precedence(peek(&s)) >= precedence(infix[i])) {  // 如果棧不為空且棧頂元素優(yōu)先級(jí)高于或等于當(dāng)前運(yùn)算符，彈出棧頂元素  postfix[j++] = pop(&s);  postfix[j++] = ' ';  }  // 當(dāng)前運(yùn)算符入棧  push(&s, infix[i++]);  }  }  // 彈出棧中剩余的所有運(yùn)算符  while (!isEmpty(&s)) {  postfix[j++] = pop(&s);  postfix[j++] = ' ';  }  // 添加字符串結(jié)束符  postfix[j] = '\0';  
}  int main() {  char infix[MAX_SIZE], postfix[MAX_SIZE * 2]; // 后綴表達(dá)式可能更長(zhǎng)，因此分配更多空間  printf("Enter an infix expression: ");  scanf("%s", infix); // 注意：這里不會(huì)處理空格和復(fù)雜輸入  infixToPostfix(infix, postfix);  printf("Postfix expression: %s\n", postfix);  return 0;  
}

2.3 后綴表達(dá)式求值

????????后綴表達(dá)式（也稱(chēng)為逆波蘭表示法或逆波蘭記法）是一種不需要括號(hào)來(lái)標(biāo)明運(yùn)算符的優(yōu)先級(jí)的數(shù)學(xué)表達(dá)式。在這種表示法中，所有的運(yùn)算符都放在操作數(shù)的后面。

????????求值后綴表達(dá)式的基本步驟如下：

• 初始化一個(gè)棧，用于存儲(chǔ)操作數(shù)。
• 從左到右掃描后綴表達(dá)式。
• 如果掃描到操作數(shù)，則將其壓入棧中。
• 如果掃描到運(yùn)算符，則從棧中彈出兩個(gè)操作數(shù)（先彈出的為右操作數(shù)，后彈出的為左操作數(shù)），將這兩個(gè)操作數(shù)作為運(yùn)算符的輸入進(jìn)行運(yùn)算，然后將結(jié)果壓回棧中。
• 重復(fù)步驟2-4，直到后綴表達(dá)式掃描完畢。
• 棧中剩下的元素就是表達(dá)式的值。

????????示例：

????????后綴表達(dá)式：3 4 + 5 *

????????求值過(guò)程：

1. 掃描到?3，壓入棧：[3]
2. 掃描到?4，壓入棧：[3, 4]
3. 掃描到?+，彈出?4?和?3，計(jì)算?3 + 4?得到?7，壓入棧：[7]
4. 掃描到?5，壓入棧：[7, 5]
5. 掃描到?*，彈出?5?和?7，計(jì)算?7 * 5?得到?35，壓入棧：[35]
6. 掃描完畢，棧中元素?35?即為表達(dá)式的值。

????????下面是實(shí)現(xiàn)代碼（以上述示例為例）：

#include <stdio.h>  
#include <stdlib.h>  
#include <ctype.h>  
#include <string.h>  #define MAX_STACK_SIZE 100  typedef struct {  double data[MAX_STACK_SIZE];  int top;  
} Stack;  // 初始化棧  
void initStack(Stack *s) {  s->top = -1;  
}  // 判斷棧是否為空  
int isEmpty(Stack *s) {  return s->top == -1;  
}  // 壓棧操作  
void push(Stack *s, double value) {  if (s->top >= MAX_STACK_SIZE - 1) {  printf("Stack overflow\n");  exit(1);  }  s->data[++s->top] = value;  
}  // 彈棧操作  
double pop(Stack *s) {  if (isEmpty(s)) {  printf("Stack underflow\n");  exit(1);  }  return s->data[s->top--];  
}  // 求值后綴表達(dá)式  
double evaluatePostfix(const char *postfix) {  Stack s;  initStack(&s);  const char *token = strtok((char *)postfix, " "); // 假設(shè)操作符和操作數(shù)之間用空格分隔  while (token != NULL) {  if (isdigit(token[0])) { // 如果是操作數(shù)  double value = atof(token);  push(&s, value);  } else { // 如果是運(yùn)算符  double rightOperand = pop(&s); // 彈出右操作數(shù)  double leftOperand = pop(&s); // 彈出左操作數(shù)  switch (token[0]) {  case '+':  push(&s, leftOperand + rightOperand);  break;  case '-':  push(&s, leftOperand - rightOperand);  break;  case '*':  push(&s, leftOperand * rightOperand);  break;  case '/':  if (rightOperand != 0.0) {  push(&s, leftOperand / rightOperand);  } else {  printf("Error: Division by zero\n");  exit(1);  }  break;  default:  printf("Error: Unknown operator\n");  exit(1);  }  }  token = strtok(NULL, " "); // 繼續(xù)獲取下一個(gè)token  }  if (!isEmpty(&s)) {  return pop(&s); // 棧中剩下的元素就是表達(dá)式的值  } else {  printf("Error: Invalid postfix expression\n");  exit(1);  }  
}  int main() {  const char *postfix = "3 4 + 5 *";  double result = evaluatePostfix(postfix);  printf("Result: %lf\n", result);  return 0;  
}

3? 棧在遞歸中的應(yīng)用

3.1 棧在函數(shù)調(diào)用中的作用

• 參數(shù)傳遞：當(dāng)調(diào)用一個(gè)函數(shù)時(shí)，需要傳遞參數(shù)給該函數(shù)。這些參數(shù)會(huì)被壓入棧中，以便函數(shù)內(nèi)部能夠訪問(wèn)和使用它們。
• 局部變量分配：函數(shù)內(nèi)部定義的局部變量會(huì)在棧上分配空間。這些變量的生命周期與函數(shù)的執(zhí)行周期相同，當(dāng)函數(shù)執(zhí)行完畢后，這些局部變量所占用的?？臻g會(huì)被自動(dòng)釋放。
• 保存調(diào)用的返回地址：在函數(shù)調(diào)用時(shí)，CPU需要知道函數(shù)執(zhí)行完畢后應(yīng)該返回到哪個(gè)位置繼續(xù)執(zhí)行。這個(gè)返回地址會(huì)被保存在棧中，以便函數(shù)執(zhí)行完畢后能夠正確地返回到調(diào)用它的位置。
• 保存寄存器以供恢復(fù)：在函數(shù)調(diào)用和返回的過(guò)程中，CPU的寄存器狀態(tài)會(huì)發(fā)生變化。為了能夠在函數(shù)返回后恢復(fù)原來(lái)的寄存器狀態(tài)，棧會(huì)保存這些寄存器的值。

3.2 棧在函數(shù)調(diào)用中的工作原理

• 函數(shù)調(diào)用：當(dāng)調(diào)用一個(gè)函數(shù)時(shí)，系統(tǒng)首先會(huì)創(chuàng)建一個(gè)新的棧幀（stack frame）來(lái)保存該函數(shù)的執(zhí)行環(huán)境。這個(gè)棧幀包含了函數(shù)的返回地址、參數(shù)、局部變量等信息。然后，系統(tǒng)會(huì)將當(dāng)前程序的執(zhí)行狀態(tài)（如返回地址、寄存器狀態(tài)等）壓入棧中，以便在函數(shù)執(zhí)行完畢后能夠恢復(fù)。
• 函數(shù)執(zhí)行：在函數(shù)執(zhí)行過(guò)程中，函數(shù)會(huì)訪問(wèn)棧幀中的參數(shù)和局部變量，并根據(jù)需要進(jìn)行計(jì)算和操作。同時(shí)，如果函數(shù)內(nèi)部調(diào)用了其他函數(shù)，系統(tǒng)也會(huì)為這些被調(diào)用的函數(shù)創(chuàng)建新的棧幀，并將當(dāng)前函數(shù)的執(zhí)行狀態(tài)壓入棧中保存。
• 函數(shù)返回：當(dāng)函數(shù)執(zhí)行完畢或者遇到return語(yǔ)句時(shí)，系統(tǒng)會(huì)彈出當(dāng)前函數(shù)的棧幀，并根據(jù)棧幀中的返回地址返回到調(diào)用它的位置繼續(xù)執(zhí)行。在返回之前，系統(tǒng)還會(huì)恢復(fù)調(diào)用該函數(shù)時(shí)的寄存器狀態(tài)。

? ? ? ? 下面將給出一個(gè)例子：

? ? ? ? 例如：階乘，大家可以自行調(diào)試；

#include <stdio.h>int step(int n){if(n==1)return 1;elsereturn n*step(n-1);
}int main(){int n,s;scanf("%d",&n);s=step(n);printf("%d",s);
}

4? 總結(jié)

????????在本文中，我們深入探討了棧這一數(shù)據(jù)結(jié)構(gòu)及其在各種應(yīng)用場(chǎng)景中的重要作用。棧作為一種后進(jìn)先出（LIFO）的數(shù)據(jù)結(jié)構(gòu)，其獨(dú)特的操作方式——壓棧（push）和彈棧（pop），使得它在計(jì)算機(jī)科學(xué)和軟件開(kāi)發(fā)中占據(jù)了不可或缺的地位。

????????詳細(xì)討論了棧在多個(gè)領(lǐng)域中的應(yīng)用。其中，后綴表達(dá)式的求值是一個(gè)經(jīng)典的棧應(yīng)用示例。在這個(gè)問(wèn)題中，我們利用棧來(lái)存儲(chǔ)操作數(shù)，并通過(guò)操作數(shù)的彈出和結(jié)果的壓入，實(shí)現(xiàn)了表達(dá)式的正確計(jì)算。這種方法不僅簡(jiǎn)化了表達(dá)式的處理流程，而且提高了計(jì)算效率。

????????此外，棧還在函數(shù)調(diào)用、遞歸等方面發(fā)揮著重要作用。在函數(shù)調(diào)用中，棧用于存儲(chǔ)局部變量和返回地址，確保函數(shù)能夠正確地返回并繼續(xù)執(zhí)行。在遞歸算法中，棧用于保存遞歸調(diào)用的中間結(jié)果，從而避免重復(fù)計(jì)算。

????????綜上所述，棧作為一種基本而強(qiáng)大的數(shù)據(jù)結(jié)構(gòu)，在各個(gè)領(lǐng)域都有著廣泛的應(yīng)用。通過(guò)學(xué)習(xí)和掌握棧的使用方法和應(yīng)用場(chǎng)景，我們能夠更好地解決實(shí)際問(wèn)題，提高編程效率。