数据结构—2.栈的应用
一、应用举例1
-
继续上一次的内容。上一次举的例子是，用栈来实现逆波兰表示法，但是，当时我们是自己将中缀表示法（通常用的数学表示法）转换为了后缀表示法，这次，我们尝试用栈的知识，写程序实现将一个___中缀表示法的表达式转换为后缀表示法___。
-
首先，我们是如何将一个中缀表达式转换为后缀表达式的呢？如上次的例子：（1 + 2）* （3 - 4），首先：从左往右看，遇到第一个左括号，忽略。遇到数字1，直接打印输出，遇到运算符+，入栈保存，遇到数字2，也直接打印输出。遇到右括号），将刚才那个+运算符出栈。遇到运算符入栈保存，继续3前面的左括号（，继续忽略，数字3打印输出，运算符-入栈保存，数字4打印输出，遇到右括号），出栈。此时，打印出的内容是：12+34-，是的，运算符称号还没有出栈，我们将原来的表达式再加上一个括号，（（1 + 2） （3 - 4）），即：最外层的括号的左括号忽略，右括号时，执行出栈操作。到此：12+34-*。
-
继续总结刚才的思维过程：
对于一个中缀表达式：
1、从左往右处理；
2、遇见左括号直接忽略；
3、遇见数字，直接打印输出；
4、遇见运算符，入栈；
5、遇见右括号，此时出栈；
6、在总的表达式上在加一个括号。
-
代码实现
/* * @name 栈的应用：中缀表达式转换为后缀表达式。 * @Date 2021年11月21 * @Author 机器人工程师sgk */ #include <stdio.h> #include <string.h> //栈，其实就是数组。所以先定义一个数组。 char stack[100]; int top = 0; void push(char c); char pop(void); int is_empty(void); int main(void) { char temp[100]; int i, len; printf("Please enter a calcuate expression:\n"); gets(temp); len = strlen(temp); for(i = 0; i < len; i++) { if(temp[i] == '(') continue; else if((temp[i] >= '0') && (temp[i] <= '9')) printf("%c", temp[i]); else if((temp[i] == '+') || (temp[i] == '-') || (temp[i] == '*')) push(temp[i]); else if(temp[i] == ')') printf("%c", pop()); } printf("\n"); return 0; } /* * @name push * @brief 将数据压入栈，来一个压一个，实际就是数组标号往后移动。 * @param char 型数据 * @retval None */ void push(char c) { stack[top++] = c;//定义一个变量，表示栈顶。 } /* * @name pop * @brief 出栈，将数据弹出。 * @param None * @retval char 型数据。 */ char pop(void) { return stack[--top];//调用一次，将栈顶元素弹出一个。--top } /* * @name is_empty * @brief 判断栈是否为空。 * @param None * @retval int型数据类型 */ int is_empty(void) { return top == 0; }
运行结果：输入（（1+2）*（3-4））
mid_to_last.c:24:2: warning: implicit declaration of function ‘gets’; did you mean ‘fgets’? [-Wimplicit-function-declaration]
gets(temp);
^~~~
fgets
/tmp/ccw1eVAY.o：在函数‘main’中：
mid_to_last.c:(.text+0x30): 警告： the `gets' function is dangerous and should not be used.
Please enter a calcuate expression:
((1+2)*(3-4))
12+34-*
二、应用2
-
括号的匹配
当一个表达式中有很多括号时，我们可以一眼看出那两个括号是一对儿，但如何让计算机判断出来呢？在此利用栈的特点，写一个括号匹配的程序。
举例我的表达式长这样：（1+2）*（3-4），从左到右给每一个符号从零排序有：0、1、2、3、4、5、6、7、8、9、10。左括号0与右括号4是一对儿，左括号6与右括号10是一对儿。好，如何写程序呢？当我在遍历字符时遇到左括号时，将左括号的序号入栈，直到遇到下一个右括号时出栈并且打印其对应的序号。
-
代码实现：
-
/* * @name 栈的实现 * @Date 2021年11月20日 * @Author 机器人工程师sgk */ #include <stdio.h> #include <string.h> //栈，其实就是数组。所以先定义一个数组。 char stack[100]; int top = 0; void push(int c); int pop(void); int is_empty(void); int main(void) { char temp[100]; int i, len; printf("Please en a calculate expression:\n"); gets(temp); len = strlen(temp); for(i = 0; i < len; i++) { if(temp[i] == '(') push(i); else if(temp[i] == ')') printf("%d %d\n", pop(), i); // else // continue; } printf("\n"); return 0; } /* * @name push * @brief 将数据压入栈，来一个压一个，实际就是数组标号往后移动。 * @param char 型数据 * @retval None */ void push(int c) { stack[top++] = c;//定义一个变量，表示栈顶。 } /* * @name pop * @brief 出栈，将数据弹出。 * @param None * @retval char 型数据。 */ int pop(void) { return stack[--top];//调用一次，将栈顶元素弹出一个。--top } /* * @name is_empty * @brief 判断栈是否为空。 * @param None * @retval int型数据类型 */ int is_empty(void) { return top == 0; }运行结果：
Please en a calculate expression: (1+2)*(3-4) 0 4 6 10
运行结果：
Please en a calculate expression:
((()))()
2 3
1 4
0 5
6 7
三、应用3
- 十进制转换为二进制
这个就不解释了，太熟悉了。无论是拿手算还是通过计算机算，这里利用栈的知识模拟下计算机是如何实现十进制转换为二进制的。
-
编程思路：
1、对要转换的数进行不为0判断，然后进行取余运算，然后将余数入栈，更新该数。
2、重复上面的步骤，直到该数为0，然后，判断栈不为空时，出栈并且打印输出，输出结果即为转换结果。
-
代码实现
/* * @name 栈的实现:十进制数转换为二进制。 * @Date 2021年11月20日 * @Author 机器人工程师sgk */ #include <stdio.h> #include <string.h> //栈，其实就是数组。所以先定义一个数组。 char stack[100]; int top = 0; void push(int c); int pop(void); int is_empty(void); int main(void) { int num;//用来保存要转换的十进制数。 printf("Please enter a calculate expression:\n"); scanf("%d", &num); while(num != 0) { push(num % 2); num /= 2; } while(!is_empty()) { printf("%d", pop()); } printf("\n"); return 0; } /* * @name push * @brief 将数据压入栈，来一个压一个，实际就是数组标号往后移动。 * @param char 型数据 * @retval None */ void push(int c) { stack[top++] = c;//定义一个变量，表示栈顶。 } /* * @name pop * @brief 出栈，将数据弹出。 * @param None * @retval char 型数据。 */ int pop(void) { return stack[--top];//调用一次，将栈顶元素弹出一个。--top } /* * @name is_empty * @brief 判断栈是否为空。 * @param None * @retval int型数据类型 */ int is_empty(void) { return top == 0; }
运行结果：
Please enter a calculate expression:
38
100110
四、应用4
-
回文判定
什么是回文数呢？如下图所示：
举例比如：abccba、abba、abcdcba…
-
编程思路
首先，回文就像一个镜像一样，它本身个数就有基数或者偶数。我们将要判断的回文数的前一半部分保存起来，然后与后一半部分进行是否相同的比较。
显而易见，这里回文数的规律与栈的规律（先入后出）简直很巧妙。
-
代码实现：
/* * @name 栈的实现:回文数的判断。 * @Date 2021年11月20日 * @Author 机器人工程师sgk */ #include <stdio.h> #include <string.h> //栈，其实就是数组。所以先定义一个数组。 char stack[100]; int top = 0; void push(char c); char pop(void); int is_empty(void); int is_palindrom(char *pt); int main(void) { char temp[100]; printf("Please enter a string:\n"); gets(temp); if(is_palindrom(temp)) printf("str is a palindrom.\n"); else printf("str is not a palindrom.\n"); printf("str is not a palindrom.\n"); return 0; } /* * @name push * @brief 将数据压入栈，来一个压一个，实际就是数组标号往后移动。 * @param char 型数据 * @retval None */ void push(char c) { stack[top++] = c;//定义一个变量，表示栈顶。 } /* * @name pop * @brief 出栈，将数据弹出。 * @param None * @retval char 型数据。 */ char pop(void) { return stack[--top];//调用一次，将栈顶元素弹出一个。--top } /* * @name is_empty * @brief 判断栈是否为空。 * @param None * @retval int型数据类型 */ int is_empty(void) { return top == 0; } /* * @name is_palindrom * @brief 判断字符串是否为回文？ * @param char 类型的字符指针 * @retval int型数据类型 */ int is_palindrom(char *pt) { int i, len; len = strlen(pt); for(i = 0; i < len / 2; i++) push(pt[i]);//将字符串前一半入栈。 if(len % 2)//如果字符串长度为奇数，则跳过那个序号为奇数的字符。 i++; while(!is_empty())//当栈不为空时，进行比较。 { if(pop() == pt[i])//因为执行一次出栈，栈顶序号减1，所以正好将出栈数据与后半部分字符串进行比较了。 i++; else return 0; } return 1;//如果是回文返回1。 }
-
运行结果：
Please enter a string:
12345654321
str is a palindrom.
运行结果：
Please enter a string:
abcdcba
str is a palindrom.
至此，栈相关的学习告一段落。后面进行队列的学习。