ToB企服应用市场:ToB评测及商务社交产业平台

标题: 栈和相关算法 [打印本页]
作者: 吴旭华    时间: 2024-4-9 14:59
标题: 栈和相关算法
栈

栈是一种抽象数据结构（ADT），其主要特性是后进先出LIFO(Last in First out)
可以用数组、链表实现，本质就是对一个列表进行后进先出的操作
栈的操作主要有push入栈、pop出栈、isEmpty判空、getTop获取栈顶元素
数组实现

首先进行最基本的数据结构和操作定义：
  1. //栈空条件
  2. top = -1
  3. //栈满条件
  4. top >= MAX - 1
复制代码
在stack.h头文件中定义栈的结构体和声明一些操作函数。一个栈由存放数据的数组data和栈顶指针top组成
  1. /*stack.h*/
  2. #ifndef __STACK_H__
  3. #define __STACK_H__
  5. #define MAX 10
  7. typedef struct stackNode {
  8.     int data[MAX];
  9.     int top;
  10. }Stack;
  12. int initStack(Stack* S);        //初始化栈
  13. int Push(Stack* S, int value);        //入栈
  14. int Pop(Stack* S);        //出栈
  15. int isEmpty(Stack S);        //判空
  16. int getTop(Stack S);        //获取栈顶元素
  18. #endif
  19. //为了防止重复引用一个头文件，使用预编译宏规范
复制代码
操作实现代码：
  1. /*stack.c*/
  2. #include <stdio.h>
  3. #include "stack.h"
  5. int initStack(Stack* S) {
  6.     S->top = -1;
  7.     return 1;
  8. }
  10. int isEmpty(Stack S) {
  11.     if(S.top == -1)
  12.     {
  13.         printf("stack is null\n");
  14.         return 1;
  15.     }
  16.     return 0;
  17. }
  19. /*
  20. 入栈时判断栈是否已满，由于本次实现栈顶指针指向的是最后一个入栈的元素，因此判断条件为top <= MAX - 1
  21. 满足入栈条件时则加入data数组，并top+1
  22. */
  23. int Push(Stack* S, int value) {
  24.     if(S->top >= MAX - 1)
  25.         return 0;
  26.     S->data[++S->top] = value;
  28.     return 1;
  29. }
  30. /*
  31. 出栈时先判断栈是否为空，接着下标减1
  32. */
  33. int Pop(Stack* S) {
  34.     if(isEmpty(*S))
  35.     {
  36.         printf("stack null\n");
  37.         return 0;
  38.     }
  39.     S->top--;
  40.     return 1;
  41. }
  43. int getTop(Stack S) {
  44.     if(isEmpty(S))
  45.         return 0;
  46.     return S.data[S.top];
  47. }
  49. void Print(Stack S) {
  50.     int i = 0;
  51.     if(isEmpty(S))
  52.     {
  53.         printf("stack null\n");
  54.         return;
  55.     }
  56.     for(;i <= S.top;i++)
  57.         printf("%d\t", S.data[i]);
  58.     printf("\n");
  59. }
  61. //测试代码
  62. int main() {
  63.     Stack S;
  64.     initStack(&S);
  65.     Push(&S, 1);
  66.     Push(&S, 2);
  67.     Push(&S, 3);
  68.     Push(&S, 4);
  69.     Push(&S, 5);
  70.     Push(&S, 6);
  71.     Push(&S, 7);
  72.     Push(&S, 8);
  73.     Push(&S, 9);
  74.     Push(&S, 10);
  75.     Push(&S, 11);
  77.     Print(S);
  78.     printf("%d\n", getTop(S));
  79.     return 0;
  80. }
复制代码
表达式计算

1.中缀表达式转后缀表达式

思路：从左到右遍历一次中缀表达式，按下面的算法进行转换，将中缀表达式转换为后缀表达式
算法：
（1）字符为操作数
加入后缀表达式，在这还需加入一些逻辑来获取大于等于10的数字或者小数，比如循环读取连续的数字组成一个完整的数字，然后用空格或其他操作数分隔
（2）字符为左括号
直接入栈
（3）字符为右括号
连续出栈，并将出栈元素加入后缀表达式，直到栈顶元素为左括号，将左括号出栈但不加入后缀表达式
（4）字符为运算符
若栈空，直接入栈。
若栈非空，判断运算符优先级是否高于栈顶运算符，高于则入栈，否则连续出栈，直到该运算符优先级高于栈顶运算符或栈空
（5）遍历完中缀表达式后，还需判断栈是否非空，非空则将全部元素出栈，加入后缀表达式
  1. void Reserse(Link head) {
  2.     Link temp = head;
  3.    
  4.     if(!head) return;
  5.     //为了方便演示，直接使用的c++的标准库中的栈定义
  6.     stack<Link> S;
  7.    
  8.     //首先将链表所有节点入栈
  9.     while(temp != NULL) {
  10.         S.push(temp);
  11.         temp = temp->next;
  12.     }
  13.    
  14.     //获取栈顶节点，最后一个入栈的即为新的链表头节点
  15.     temp = S.top();
  16.     S.pop();
  17.     head = temp;        //此时head和temp都指向新链表的第一个节点
  18.    
  19.     while(!S.empty()) {
  20.         //当栈非空时，将temp->next指针指向当前栈顶的节点
  21.         //出栈一次
  22.         //更新temp指针，使其指向刚反转的新节点
  23.         temp->next = S.top();
  24.         S.pop();
  25.         temp = temp->next;
  26.         }
  27.     //最后将最后一个节点的next置为NULL
  28.     temp->next = NULL;
  29. }
复制代码
2.后缀表达式计算

算法：
（1）字符为操作数
直接入栈
（2）字符为运算符
连续出栈两次，与运算符进行运算，结果入栈
（3）重复以上步骤直到遍历完后缀表达式
  1. string InfixToPostfix(string expression) {
  2.     stack<char> S;
  3.     string postfix = "";
  5.     for(int i = 0;i < expression.length();i++) {
  6.         if(expression[i] == ' ' || expression[i] == ',') continue;
  7.         
  8.         if(IsOperator(expression[i])) { //字符=运算符
  9.             while(!S.empty() && '(' != S.top() && !HigherPrecedence(S.top(), expression[i])) {
  10.                 //当栈非空，且操作符优先级未大于栈顶元素时，出栈并加入postfix
  11.                 postfix += S.top();
  12.                 S.pop();
  13.             }
  14.             S.push(expression[i]);
  15.         }else if(IsOperand(expression[i])) {    //字符=操作数
  16.             while(IsOperand(expression[i])) {
  17.                 postfix += expression[i];
  18.                 i += 1;
  19.             }
  20.             postfix += ' ';
  21.             i--;
  22.         }else if('(' == expression[i]) {    //字符=左括号
  23.             S.push(expression[i]);
  24.         }else if(')' == expression[i]) {
  25.             while (!S.empty() && S.top() != '(')    //字符=右括号
  26.             {
  27.                 postfix += S.top();
  28.                 S.pop();
  29.             }
  30.             S.pop();
  31.         }
  32.     }
  33.             //将剩余元素出栈
  34.     while(!S.empty()) {
  35.         postfix += S.top();
  36.         S.pop();
  37.     }
  38.     return postfix;
  39. }
复制代码
3.完整代码

[code]#include #include #include using namespace std;//计算后缀表达式函数int EvaluetionPostfix(string expression);//二元表达式计算int PerformOperation(char operation, int operand1, int operand2);//中缀转后缀string InfixToPostfix(string expression);//运算符判断bool IsOperator(char c);//操作数判断bool IsOperand(char c);//获取运算符权重int GetOperatorWeight(char op);//运算符优先级比较bool HigherPrecedence(char op1, char op2);int main() {    string expression = "";    cout



欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/) Powered by Discuz! X3.4