• 【数据结构】栈（stack）

    栈的基本概念

    • 概念

    栈是一个线性表，栈元素具有线性关系，即前驱后继关系，但是是一种特殊的线性表，在线性表的表尾进行插入和删除操作，表尾是指栈顶，表头是指栈底。

    • 特性

    先进后出的规则

    始终只进行栈顶操作，想访问栈底数据，就需要将上面数据一个一个出栈

    栈的顺序存储

    • 基本概念

    栈的顺序存储结构简称顺序栈，它是运算受限制的顺序表。顺序栈的存储结构是：利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针 top （只是栈顶元素在顺序表的位置）

    顺序存储栈栈

    • 框架及函数声明
    1. #ifndef SEQSTACK_H
    2. #define SEQSTACK_H
    3.  
    4. #define _CRT_SECURE_NO_WARNINGS 1
    5. #include
    6. #include
    7. #include
    8.  
    9. // 数组模拟栈的顺序存储
    10. #define MAX_SIZE 1024
    11. #define SEQSTACK_TURE 1
    12. #define SEQSTACK_FALSE 0
    13.  
    14. typedef struct SEQSTACK { 
    15.     void* data[MAX_SIZE];
    16.     int size;
    17. }SeqStack;
    18.  
    19. // 初始化栈
    20. SeqStack* Init_Stack();
    21.  
    22. // 入栈
    23. void Push_Stack(SeqStack* stack, void* data);
    24.  
    25. // 返回栈顶元素
    26. void* Top_Stack(SeqStack* stack);
    27.  
    28. // 出栈
    29. void Pop_Stack(SeqStack* stack);
    30.  
    31. // 判断是否为空
    32. int IsEmpty_Stack(SeqStack* stack);
    33.  
    34. //  返回栈中元素个数
    35. int Size_Stack(SeqStack* stack);
    36.  
    37. // 清空栈
    38. void Clear_Stack(SeqStack* stack);
    39.  
    40. // 销毁
    41. void FreeSpace_Stack(SeqStack* stack);
    42.  
    43. #endif
    • 函数实现
    1. #include"SeqStack.h"
    2.  
    3. // 初始化栈
    4. SeqStack* Init_Stack(){
    5.     //(SeqStack*)Stack = (SeqStack*)malloc(sizeof(SeqStack));
    6.     SeqStack* stack = (SeqStack*)malloc(sizeof(SeqStack));
    7.     for (int i = 0; i < MAX_SIZE; i++) {
    8.         stack->data[i] = NULL;
    9.     }
    10.     stack->size = 0;
    11.     return stack;
    12. }
    13.  
    14. // 入栈
    15. void Push_Stack(SeqStack* stack, void* data){
    16.     if (stack->size == MAX_SIZE) return;
    17.     if (stack == NULL) return;
    18.     if (data == NULL)  return;
    19.  
    20.     stack->data[stack->size] = data;
    21.     stack->size++;
    22. }
    23.  
    24. // 返回栈顶元素
    25. void* Top_Stack(SeqStack* stack){
    26.     if (stack == NULL)    return NULL;
    27.     if (stack->size == 0) return NULL;
    28.  
    29.     return stack->data[stack->size - 1];
    30. }
    31.  
    32. // 出栈
    33. void Pop_Stack(SeqStack* stack){
    34.     if (stack == NULL)    return;
    35.     if (stack->size == 0) return;
    36.  
    37.     stack->data[stack->size - 1] = NULL;
    38.     stack->size--;
    39. }
    40.  
    41. // 判断是否为空
    42. int IsEmpty_Stack(SeqStack* stack){
    43.     if (stack->data == NULL) return -1;
    44.     if (stack->size == 0)    return SEQSTACK_TURE;
    45.     return SEQSTACK_FALSE;
    46. }
    47.  
    48. //  返回栈中元素个数
    49. int Size_Stack(SeqStack* stack){
    50.     if (stack == NULL) return 0;
    51.     return stack->size;
    52. }
    53.  
    54. // 清空栈
    55. void Clear_Stack(SeqStack* stack){
    56.     if (stack == NULL) return;
    57.     for (int i = 0; i < stack->size; i++) {
    58.         stack->data[i] = NULL;
    59.     }
    60.     stack->size = 0;
    61. }
    62.  
    63. // 销毁
    64. void FreeSpace_Stack(SeqStack* stack){
    65.     if (stack == NULL) return;
    66.     free(stack);
    67. }
    • 测试代码
    1. #include"SeqStack.h"
    2.  
    3. typedef struct PERSON {
    4.     char name[64];
    5.     int age;
    6. }Person;
    7.  
    8. void test() {
    9.     SeqStack* stack = Init_Stack();
    10.  
    11.     Person p1, p2, p3, p4, p5;
    12.     strcpy(p1.name, "张三");
    13.     strcpy(p2.name, "李四");
    14.     strcpy(p3.name, "王五");
    15.     strcpy(p4.name, "李华");
    16.     strcpy(p5.name, "赵六");
    17.     p1.age = 10;
    18.     p2.age = 20;
    19.     p3.age = 30;
    20.     p4.age = 40;
    21.     p5.age = 50;
    22.  
    23.     // 判断栈是否为空
    24.     if (IsEmpty_Stack(stack)) printf("栈为空\n");
    25.     else printf("栈非空\n");
    26.  
    27.     // 入栈
    28.     Push_Stack(stack, (void*)&p1);
    29.     Push_Stack(stack, (void*)&p2);
    30.     Push_Stack(stack, (void*)&p3);
    31.     Push_Stack(stack, (void*)&p4);
    32.     Push_Stack(stack, (void*)&p5);
    33.  
    34.     // 判断栈是否为空
    35.     if (IsEmpty_Stack(stack)) printf("栈为空\n");
    36.     else printf("栈非空\n");
    37.  
    38.     while (Size_Stack(stack)) {
    39.         // 访问栈顶元素
    40.         Person* person = (Person*)Top_Stack(stack);
    41.         printf("name: %s age: %d\n", person->name, person->age);
    42.         Pop_Stack(stack);
    43.     }
    44.  
    45.     FreeSpace_Stack(stack);
    46. }
    47.  
    48. int main() {
    49.     test();
    50.     return 0;
    51. }

    运行结果：

    链式存储的栈

    • 框架及函数声明
    1. #ifndef LINKSTACK_H
    2. #define LINKSTACK_H
    3.  
    4. #define _CRT_SECURE_NO_WARNINGS 1
    5.  
    6. #include 
    7. #include 
    8. #include 
    9.  
    10. // 结点
    11. typedef struct STACKNODE {
    12.     struct STACKNODE* next;
    13. }StackNode;
    14.  
    15. // 链式 栈
    16. typedef struct LINKSTACK {
    17.     StackNode head;
    18.     int size;
    19. }LinkStack;
    20.  
    21. // 初始化
    22. LinkStack* Init_Stack();
    23.  
    24. // 入栈
    25. void Push_Stack(LinkStack* stack, StackNode* data);
    26.  
    27. // 出栈
    28. void Pop_Stack(LinkStack* stack);
    29.  
    30. // 返回栈顶
    31. StackNode* Top_Stack(LinkStack* stack);
    32.  
    33. // 返回栈中元素个数
    34. int Size_Stack(LinkStack* stack);
    35.  
    36. // 清空栈
    37. void Clear_Stack(LinkStack* stack);
    38.  
    39. // 释放栈
    40. void Free_Stack(LinkStack* stack);
    41.  
    42. #endif // !LINKSTACK_H
    • 函数实现
    1. #include "LinkStack.h"
    2.  
    3. // 初始化
    4. LinkStack* Init_Stack() { 
    5.     LinkStack* stack = (LinkStack*)malloc(sizeof(LinkStack));
    6.     stack->head.next = NULL;
    7.     stack->size = 0;
    8.     return stack;
    9. }
    10.  
    11. // 入栈
    12. void Push_Stack(LinkStack* stack, StackNode* data) { 
    13.     if (stack == NULL) return;
    14.     if (data  == NULL) return;
    15.  
    16.     data->next = stack->head.next;
    17.     stack->head.next = data;
    18.     stack->size++;
    19. }
    20.  
    21. // 出栈
    22. void Pop_Stack(LinkStack* stack) {
    23.     if (stack == NULL) return;
    24.     if (stack->size == 0) return;
    25.  
    26.     // 第一个有效结点
    27.     StackNode* pNext = stack->head.next;
    28.     stack->head.next = pNext->next;
    29.  
    30.     stack->size--;
    31. }
    32.  
    33. // 返回栈顶
    34. StackNode* Top_Stack(LinkStack* stack) { 
    35.     if (stack == NULL) return NULL;
    36.     if (stack->size == 0) return NULL;
    37.  
    38.     return stack->head.next;
    39. }
    40.  
    41. // 返回栈元素个数
    42. int Size_Stack(LinkStack* stack) {
    43.     if (stack == NULL) return 0;
    44.     return stack->size;
    45. }
    46.  
    47. // 清空栈
    48. void Clear_Stack(LinkStack* stack) { 
    49.     if (stack == NULL) return;
    50.  
    51.     stack->head.next = NULL;
    52.     stack->size = 0;
    53. }
    54.  
    55. // 释放栈
    56. void Free_Stack(LinkStack* stack) {
    57.     if (stack == NULL) return;
    58.     
    59.     free(stack);
    60. }
    • 测试代码
    1. #include "LinkStack.h"
    2.  
    3. typedef struct PERSON {
    4.     StackNode node;
    5.     char name[64];
    6.     int age;
    7. }Person;
    8.  
    9. void test() {
    10.     // 创建栈
    11.     LinkStack* stack = Init_Stack();
    12.  
    13.     // 创建数据
    14.     Person p1, p2, p3, p4, p5;
    15.     strcpy(p1.name, "aaa");
    16.     strcpy(p2.name, "bbb");
    17.     strcpy(p3.name, "ccc");
    18.     strcpy(p4.name, "ddd");
    19.     strcpy(p5.name, "eee");
    20.     p1.age = 10;
    21.     p2.age = 20;
    22.     p3.age = 30;
    23.     p4.age = 40;
    24.     p5.age = 50;
    25.  
    26.     // 入栈
    27.     Push_Stack(stack, (StackNode*)&p1);
    28.     Push_Stack(stack, (StackNode*)&p2);
    29.     Push_Stack(stack, (StackNode*)&p3);
    30.     Push_Stack(stack, (StackNode*)&p4);
    31.     Push_Stack(stack, (StackNode*)&p5);
    32.  
    33.     // 返回栈中元素个数
    34.     printf("栈中元素个数: %d\n", Size_Stack(stack));
    35.  
    36.     // 出栈
    37.     while (Size_Stack(stack) > 0) {
    38.         Person* p = (Person*)Top_Stack(stack); // 返回栈顶
    39.         printf("name: %s age: %d\n", p->name, p->age);
    40.         Pop_Stack(stack); // 弹出栈顶
    41.     }
    42.     Free_Stack(stack);
    43. }
    44.  
    45. int main() {
    46.     test();
    47.     return 0;
    48. }

    运行结果：

    栈的应用

    就近匹配

    匹配左右括号，找到字符串中不匹配的位置

    • 框架及函数声明
    1. #ifndef LINKSTACK_H
    2. #define LINKSTACK_H
    3.  
    4. #include 
    5. #include 
    6. #include 
    7.  
    8. // 结点
    9. typedef struct STACKNODE {
    10.     struct STACKNODE* next;
    11. }StackNode;
    12.  
    13. // 链式栈
    14. typedef struct LINKSTACK {
    15.     StackNode head;
    16.     int size;
    17. }LinkStack;
    18.  
    19. // 初始化栈
    20. LinkStack* Init_Stack();
    21.  
    22. // 入栈
    23. void Push_Stack(LinkStack* stack, StackNode* data);
    24.  
    25. // 出栈
    26. void Pop_Stack(LinkStack* stack);
    27.  
    28. // 获取栈顶
    29. StackNode* Top_Stack(LinkStack* stack);
    30.  
    31. // 返回栈元素个数
    32. int Size_Stack(LinkStack* stack);
    33.  
    34. // 清空栈
    35. void Clear_Stack(LinkStack* stack);
    36.  
    37. // 释放栈
    38. void Free_Stack(LinkStack* stack);
    39.  
    40. #endif // !LINKSTACK_H
    • 函数实现
    1. #include "LinkStack.h"
    2.  
    3. // 初始化栈
    4. LinkStack* Init_Stack() {
    5.     LinkStack* stack = (LinkStack*)malloc(sizeof(LinkStack));
    6.     stack->head.next = NULL;
    7.     stack->size = 0;
    8.     return stack;
    9. }
    10.  
    11. // 入栈
    12. void Push_Stack(LinkStack* stack, StackNode* data) { 
    13.     if (stack == NULL) return;
    14.     if (data == NULL)  return;
    15.  
    16.     data->next = stack->head.next;
    17.     stack->head.next = data;
    18.     stack->size++;
    19. }
    20.  
    21. // 出栈
    22. void Pop_Stack(LinkStack* stack) {
    23.     if (stack == NULL) return;
    24.     if (stack->size == 0) return;
    25.  
    26.     // 记录第一个有效的结点
    27.     StackNode* pNext = stack->head.next;
    28.     stack->head.next = pNext;
    29.     stack->size--;
    30. }
    31.  
    32. // 获取栈顶
    33. StackNode* Top_Stack(LinkStack* stack) { 
    34.     if (stack == NULL) return NULL;
    35.  
    36.     return stack->head.next;
    37. }
    38.  
    39. // 返回栈元素个数
    40. int Size_Stack(LinkStack* stack) {
    41.     if (stack == NULL) return 0;
    42.     return stack->size;
    43. }
    44.  
    45. // 清空栈
    46. void Clear_Stack(LinkStack* stack) {
    47.     if (stack == NULL) return;
    48.     stack->size = 0;
    49. }
    50.  
    51. // 释放栈
    52. void Free_Stack(LinkStack* stack) {
    53.     if (stack == NULL) return;
    54.     free(stack);
    55. }
    • 测试代码
    1. #include "LinkStack.h"
    2.  
    3. typedef struct MyChar {
    4.     StackNode node;
    5.     char* str;
    6.     int index;
    7. }MyChar;
    8.  
    9. int IsLeft(char c) {
    10.     return c == '(';
    11. }
    12.  
    13. int IsRight(char c) {
    14.     return c == ')';
    15. }
    16.  
    17. void ShowError(char* str, int pos) {
    18.     printf("%s\n", str);
    19.     for (int i = 0; i < pos; i++) {
    20.         printf(" ");
    21.     }
    22.     printf("A\n");
    23. }
    24.  
    25. void test() {
    26.     char* str = "((1+2)+)()(())";
    27.     char* p = str;
    28.     
    29.     int index = 0;
    30.     // 创建栈
    31.     LinkStack* stack = Init_Stack();
    32.     while (*p != '\0') {
    33.         // 左括号 ( 进栈
    34.         if (IsLeft(*p)) {
    35.             // 创建字符数据
    36.             MyChar* mychar = (MyChar*)malloc(sizeof(MyChar));
    37.             mychar->str = p;
    38.             mychar->index = index;
    39.             Push_Stack(stack, (StackNode*)mychar);
    40.             free(mychar);
    41.         }
    42.         // 右括号 ) 出栈
    43.         if (IsRight(*p)) {
    44.             // 栈内要有括号
    45.             if (Size_Stack(stack) > 0) {
    46.                 Pop_Stack(stack); // 弹出栈顶元素
    47.             }
    48.             else {
    49.                 printf("右括号没有匹配的左括号\n");
    50.                 ShowError(str, index);
    51.                 break;
    52.             }
    53.         }
    54.         p++;
    55.         index++;
    56.     }
    57.     if (Size_Stack(stack) > 0) {
    58.         MyChar* mychar = (MyChar*)Top_Stack(stack);
    59.         printf("左括号没有匹配的右括号\n");
    60.         ShowError(str, (mychar->index) - Size_Stack(stack) + 1);
    61.         Pop_Stack(stack);
    62.         free(mychar);
    63.     }
    64.     else {
    65.         printf("括号匹配成功\n");
    66.     }
    67.     Free_Stack(stack);
    68. }
    69.  
    70. int main() {
    71.     test();
    72.     return 0;
    73. }

    运行结果：

    中缀表达式

    后缀表达式与中缀表达式

    • 将运算符放在数字后面叫后缀表达式 ---> 符合及计算机运算
    • 平时所写的数学表达式叫中缀表达式 ---> 符合直观思维逻辑

    实例（中缀表达式 转化为 后缀表达式）

    • 1 + 2      --->  1 2 +
    • 1 + 2 * 3 --->  1 2 3 * +

    中缀表达式算法

    遍历中缀表达式中所有的数字和符号

    • 对于数字：直接输出
    • 对于符号：
    1. 左括号：直接进栈
    2. 运算符号：与栈顶符号进行优先级比较        
      • 该符号优先级高：该运算符入栈（默认栈底为左括号，左括号优先级最低）
      • 该符号优先级不高：将栈顶符号弹出并输出（直到满足条件1），之后该符号进栈
    • 对于右括号：将栈顶符号弹出并输出，直到匹配左括号

    遍历结束：将栈中的所有符号弹出并输出                        

    • 代码示例
    1. #include "LinkStack.h"
    2.  
    3. typedef struct Mychar {
    4.     StackNode node;
    5.     char* str;
    6. }MyChar;
    7.  
    8. // 创建 MyChar
    9. MyChar* CreateMyChar(char* p) {
    10.     MyChar* mychar = (MyChar*)malloc(sizeof(MyChar));
    11.     if (mychar != NULL) {
    12.         mychar->str = p;
    13.         return mychar;
    14.     }
    15.     else return NULL;
    16. }
    17.  
    18. // 数字
    19. int Is_Number(char c) {
    20.     return (c >= '0' && c <= '9');
    21. }
    22.  
    23. // 数字操作
    24. void Number_Operate(char* p) {
    25.     printf("%c", *p);
    26. }
    27.  
    28. // 左括号
    29. int Is_Left(char c) {
    30.     return (c == '(');
    31. }
    32.  
    33. // 左括号操作
    34. void Left_Operate(LinkStack* stack, char* p) {
    35.     // 进栈
    36.     Push_Stack(stack, (StackNode*)CreateMyChar(p));
    37. }
    38.  
    39. // 右括号
    40. int Is_Right(char c) {
    41.     return (c == ')');
    42. }
    43.  
    44. // 右括号操作
    45. void Right_Operate(LinkStack* stack) {
    46.     // 先判断栈中有没有元素
    47.     while (Size_Stack(stack) > 0) {
    48.         MyChar* mychar = (MyChar*)Top_Stack(stack);
    49.         // 匹配到左括号
    50.         if (Is_Left(*(mychar->str))) {
    51.             // 左括号出栈
    52.             Pop_Stack(stack);
    53.             // 结束
    54.             break;
    55.         }
    56.         // 输出
    57.         printf("%c", *(mychar->str));
    58.         // 弹出
    59.         Pop_Stack(stack);
    60.     }
    61. }
    62.  
    63.  
    64. // 运算符
    65. int Is_Opertaor(char c) {
    66.     return (c == '+' || c == '-' ||
    67.         c == '*' || c == '/');
    68. }
    69.  
    70. // 返回运算符优先级
    71. int GetPriority(char c) {
    72.  
    73.     if (c == '*' || c == '/') {
    74.         return 2;
    75.     }
    76.     if (c == '+' || c == '-') {
    77.         return 1;
    78.     }
    79.     return 0;
    80. }
    81.  
    82. // 运算符操作
    83. void Operator_Operate(LinkStack* stack, char* p) {
    84.     // 取出栈顶符号
    85.     MyChar* mychar = (MyChar*)Top_Stack(stack);
    86.     // 栈顶没有符号，该符号入栈
    87.     if (mychar == NULL) {
    88.         Push_Stack(stack, (StackNode*)CreateMyChar(p));
    89.         return;
    90.     }
    91.  
    92.     // 栈顶优先级低于当前符号优先级，该符号入栈
    93.     if (GetPriority(*(mychar->str)) < GetPriority(*p)) {
    94.         Push_Stack(stack, (StackNode*)CreateMyChar(p));
    95.         return;
    96.     }
    97.  
    98.     // 栈顶优先级不低于当前符号优先级
    99.     else {
    100.         while (Size_Stack(stack) > 0) {
    101.  
    102.             MyChar* mychar2 = (MyChar*)Top_Stack(stack);
    103.  
    104.             // 直到栈顶符号优先级低于该符号，该符号入栈
    105.             if (GetPriority(*(mychar2->str)) < GetPriority(*p)) {
    106.                 Push_Stack(stack, (StackNode*)CreateMyChar(p));
    107.                 break;
    108.             }
    109.             printf("%c", *(mychar2->str));
    110.             Pop_Stack(stack);
    111.         }
    112.     }
    113. }
    114.  
    115. // 弹出剩余的符号
    116. void Left_Over_Stack(LinkStack* stack) {
    117.     while (Size_Stack(stack) > 0) {
    118.         MyChar* mychar = (MyChar*)Top_Stack(stack);
    119.         printf("%c", *(mychar->str));
    120.         Pop_Stack(stack);
    121.     }
    122. }
    123.  
    124. void test() {
    125.     char* str = "3+(2-1)*5/6";
    126.     char* p = str;
    127.  
    128.     LinkStack* stack = Init_Stack();
    129.  
    130.     while (*p != '\0') {
    131.  
    132.         // 数字(输出)
    133.         if (Is_Number(*p)) {
    134.             Number_Operate(p);
    135.         }
    136.  
    137.         // 左括号(入栈)
    138.         if (Is_Left(*p)) {
    139.             Left_Operate(stack, p);
    140.         }
    141.  
    142.         // 右括号(出栈直到左括号)
    143.         if (Is_Right(*p)) {
    144.             Right_Operate(stack);
    145.         }
    146.  
    147.         // 运算符(与栈顶比较)
    148.         if (Is_Opertaor(*p)) {
    149.             Operator_Operate(stack, p);
    150.         }
    151.  
    152.         p++; // 字符指针移动
    153.     }
    154.  
    155.     // 循环结束直接弹出所有符号
    156.     while (Size_Stack(stack) > 0) {
    157.         MyChar* mychar = (MyChar*)Top_Stack(stack);
    158.         printf("%c", *(mychar->str));
    159.         Pop_Stack(stack);
    160.     }
    161.     // 释放栈
    162.     FreeStack(stack);
    163. }
    164.  
    165. int main() {
    166.     test();
    167.     return 0;
    168. }

    运行结果：

    后缀表达式计算

    后缀转中缀

    遍历后缀表达式中的数字和符号

    • 对于数字：进栈
    • 对于符号：
      • 从栈中弹出右操作数
      • 从栈中弹出左操作数
      • 根据符号进行运算
      • 将运算结果压入栈中

    结束遍历：栈中的唯一数字为计算结果

    图方便直接C++的 stack 和 list 

    1. #include 
    2. #include 
    3. #include 
    4. #include 
    5.  
    6. using namespace std;
    7.  
    8. int isNumber(char c) {
    9.     return (c >= '0' && c <= '9');
    10. }
    11.  
    12. int isOperate(char c) {
    13.     return (c == '+' || c == '-' || c == '*' || c == '/');
    14. }
    15.  
    16. int priorityOperate(char c) {
    17.     if (c == '*' || c == '/') return 2;
    18.     if (c == '+' || c == '-') return 1;
    19.     return 0;
    20. }
    21.  
    22. int isLeft(char c) {
    23.     return (c == '(');
    24. }
    25.  
    26. int isRight(char c) {
    27.     return (c == ')');
    28. }
    29.  
    30. void printList(const list<char>& clist) {
    31.     for (list<char>::const_iterator it = clist.begin(); it != clist.end(); it++) {
    32.         cout << *it;
    33.     }
    34.     cout << endl;
    35. }
    36.  
    37. int main() {
    38.     char str[] = "3+(2-1)*5/6";
    39.     char* p = str;
    40.  
    41.     list<char>cList;
    42.     stack<char>cStack;
    43.  
    44.     while (*p != '\0') {
    45.         // 数字
    46.         if (isNumber(*p)) {
    47.             cList.push_back(*p);
    48.         }
    49.         // 操作符
    50.         if (isOperate(*p)) {
    51.             if (cStack.size() == 0) {
    52.                 cStack.push(*p);
    53.             }
    54.             else {
    55.                 if (priorityOperate(*p) > priorityOperate(cStack.top())) {
    56.                     cStack.push(*p);
    57.                 }
    58.                 else {
    59.                     while (cStack.size() > 0) {
    60.                         if (priorityOperate(*p) > priorityOperate(cStack.top())) {
    61.                             cStack.push(*p);
    62.                             break;
    63.                         }
    64.                         cList.push_back(cStack.top());
    65.                         cStack.pop();
    66.                     }
    67.                 }
    68.             }            
    69.         }
    70.         // 左括号
    71.         if (isLeft(*p)) {
    72.             cStack.push(*p);
    73.         }
    74.         // 右括号
    75.         if (isRight(*p)) {
    76.             // 出栈直到遇到左括号
    77.             while (cStack.size() > 0) {
    78.                 if (cStack.top() == '(') {
    79.                     cStack.pop();
    80.                     break;
    81.                 }
    82.                 cList.push_back(cStack.top());
    83.                 cStack.pop();
    84.             }
    85.         }
    86.  
    87.         p++;
    88.     }
    89.     while (cStack.size() > 0) {
    90.         cList.push_back(cStack.top());
    91.         cStack.pop();
    92.     }
    93.     printList(cList);
    94.  
    95.     // 波兰表达式处理完
    96.  
    97.     // 对 cList 中处理
    98.  
    99.     // 数字压栈
    100.     // 运算符，将栈顶数字弹出，先弹出右操作数再弹出左操作数
    101.  
    102.     // 遍历
    103.     for (list<char>::const_iterator cit = cList.begin(); cit != cList.end(); cit++) {
    104.         if (isNumber(*cit)) {
    105.             cStack.push(*cit);
    106.         }
    107.         else {
    108.             char right = cStack.top();
    109.             cStack.pop();
    110.             char left = cStack.top();
    111.             cStack.pop();
    112.             switch (*cit) {
    113.             case '+':
    114.                 cStack.push(left + right);
    115.                 break;
    116.             case '-':
    117.                 cStack.push(left - right);
    118.                 break;
    119.             case '*':
    120.                 cStack.push(left * right);
    121.                 break;
    122.             case '/':
    123.                 cStack.push(left / right);
    124.                 break;
    125.             default:
    126.                 break;
    127.             }
    128.         }
    129.     }
    130.     if (cStack.size() == 1) {
    131.         printf("ret = %c", cStack.top());
    132.         cStack.pop();
    133.     }
    134.     else {
    135.         printf("error");
    136.         printf("%zu", cStack.size());
    137.     }
    138.     system("pause");
    139.     return 0;
    140. }

  • 相关阅读:
    Ubuntu Minkowski Engine安装
    PHP8的数据封装（数据隐藏）-PHP8知识详解
    【开发工具】git服务器端安装部署+客户端配置
    jsbridge实战1：xcode swift 构建iOS app
    【面试】虚拟机栈面试题
    1.3 统计学习方法的三要素
    GetQueuedCompletionStatus返回为0，GetLastError()错误号是234
    目标检测俯瞰总览资料汇总
    万字详解Spring相关组件配置原理
    多元宇宙算法求解多目标优化问题附matlab代码(Multi-VerseOptimizer,MVO)
  • 原文地址：https://blog.csdn.net/xuan3215/article/details/126377624