• 数据结构——栈与队列

    目录

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

     2. 括号匹配问题

    3. 栈实现队列

    4. 约瑟夫环

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

    【问题描述】
     输入一个中缀表达式，表达式中有+、-、*、/四种运算以及（、），表达式中的其他符号为大写的字母。实现一个算法，得到相应的后缀表达式。

    【输入形式】
     一个式子的中缀表达式，以#结束

    【输出形式】
     相应的后缀表达式 

    【样例输入】

     A*(B-C)/D+E#

    【样例输出】

     ABC-*D/E+

    【评分标准】
     请大家在程序中写出必要的注释，如果程序没有必要的注释，将酌情扣分

    1.  
    2. #include
    3. #include
    4.  
    5. #define MAX_SIZE 100
    6. typedef struct {
    7.     char data[MAX_SIZE];
    8.     int top;
    9. }Stack;
    10.  
    11. void init(Stack *stack){
    12.     stack->top=-1;
    13. }
    14.  
    15. int isEmpty(Stack *stack){
    16.     return stack->top==-1;
    17. }
    18.  
    19. int isFull(Stack *stack){
    20.     return stack->top==MAX_SIZE-1;
    21. }
    22.  
    23. void push(Stack *stack,char c){
    24.     if(isFull(stack)){
    25.         printf("Stack overflow\n");
    26.         return;
    27.     }
    28.     stack->data[++stack->top]=c;
    29. }
    30.  
    31. char pop(Stack *stack){
    32.     if(isEmpty(stack)){
    33.         printf("Stack underflow\n");
    34.         return '\0';
    35.     }
    36.     return stack->data[stack->top--];
    37. }
    38.  
    39. int getPriority(char c){
    40.     if(c=='+'||c=='-'){
    41.         return 1;
    42.     }
    43.     else if(c=='*'||c=='/'){
    44.         return 2;
    45.     }
    46.     else{
    47.         return 0;
    48.     }
    49. }
    50.  
    51. void infixToPostfix(char *infix, char *postfix){
    52.     Stack s;
    53.     init(&s);
    54.     int i=0, j=0;
    55.     while(infix[i]!='#'){
    56.         if(infix[i]>='A'&&infix[i]<='Z'){
    57.             postfix[j++]=infix[i];
    58.         }
    59.         else if(infix[i]=='('){
    60.             push(&s, infix[i]);
    61.         }
    62.         else if(infix[i]==')'){
    63.             while(!isEmpty(&s) && s.data[s.top]!='('){
    64.                 postfix[j++]=pop(&s);
    65.             }
    66.             if(!isEmpty(&s) && s.data[s.top]=='('){
    67.                 pop(&s);
    68.             }
    69.         }
    70.         else{
    71.             while(!isEmpty(&s) && getPriority(infix[i])<=getPriority(s.data[s.top])){
    72.                 postfix[j++]=pop(&s);
    73.             }
    74.             push(&s, infix[i]);
    75.         }
    76.         i++;
    77.     }
    78.     while(!isEmpty(&s)){
    79.         postfix[j++]=pop(&s);
    80.     }
    81.     postfix[j]='\0';
    82. }
    83.  
    84. int main(){
    85.     char infix[MAX_SIZE];
    86.     scanf("%s", infix);
    87.     char postfix[MAX_SIZE];
    88.     infixToPostfix(infix, postfix);
    89.     printf("%s\n", postfix);
    90.     return 0;
    91. }

     2. 括号匹配问题

    【问题描述】

    假设一算术表达式中包括三种括号：圆括号"（"和"）"，方括号"["和"]"，花括号"{"和"}"，且三种括号可按意 次序嵌套使用，试编写程序判定输入的表达式所含的括号是否正确配对出现（已知表达式已存入数据元素为字符的顺序表中）。若匹配，则返回1，否则返回0。
    【输入形式】

    含括号的算数表达式
    【输出形式】

    1或者0

    【样例输入】

    3+(44*[5-{6*[7*（45-10）]}])

    【样例输出】

    1

    【样例说明】

    判断括号是否匹配涉及两方面，括号个数和出现次序的判定。
    【评分标准】

    1. #include 
    2. #include 
    3.  
    4. #define MAX_SIZE 100
    5.  
    6. typedef struct {
    7.     char data[MAX_SIZE];
    8.     int top;
    9. } Stack;
    10.  
    11. void init(Stack *stack) {
    12.     stack->top = -1;
    13. }
    14.  
    15. int isEmpty(Stack *stack) {
    16.     return stack->top == -1;
    17. }
    18.  
    19. int isFull(Stack *stack) {
    20.     return stack->top == MAX_SIZE - 1;
    21. }
    22.  
    23. void push(Stack *stack, char c) {
    24.     if (isFull(stack)) {
    25.         printf("Stack overflow\n");
    26.         return;
    27.     }
    28.     stack->data[++stack->top] = c;
    29. }
    30.  
    31. char pop(Stack *stack) {
    32.     if (isEmpty(stack)) {
    33.         printf("Stack underflow\n");
    34.         return '\0';
    35.     }
    36.     return stack->data[stack->top--];
    37. }
    38.  
    39. int isMatching(char left, char right) {
    40.     if (left == '(' && right == ')') {
    41.         return 1;
    42.     } else if (left == '[' && right == ']') {
    43.         return 1;
    44.     } else if (left == '{' && right == '}') {
    45.         return 1;
    46.     } else {
    47.         return 0;
    48.     }
    49. }
    50.  
    51. int isParenthesesMatching(char *expression) {
    52.     Stack stack;
    53.     init(&stack);
    54.     int i;
    55.     int length = strlen(expression);
    56.     for ( i = 0; i < length; i++) {
    57.         char c = expression[i];
    58.         if (c == '(' || c == '[' || c == '{') {
    59.             push(&stack, c);
    60.         } else if (c == ')' || c == ']' || c == '}') {
    61.             if (isEmpty(&stack)) {
    62.                 return 0;
    63.             }
    64.             char top = pop(&stack);
    65.             if (!isMatching(top, c)) {
    66.                 return 0;
    67.             }
    68.         }
    69.     }
    70.     return isEmpty(&stack);
    71. }
    72.  
    73. int main() {
    74.     char expression[MAX_SIZE];
    75.     fgets(expression, MAX_SIZE, stdin);
    76.     int result = isParenthesesMatching(expression);
    77.     printf("%d\n", result);
    78.     return 0;
    79. }

    3. 栈实现队列

    【问题描述】

    请使用栈类实现队列的类。

    【输入形式】

    第一行一个整数n，

    接下来n行，每行一个整数，依次表示已经在队列中的数。

    接下来一行，一个整数m。

    接下来m行，有两种情况：1. 一个整数，请将其入列。2. 字符串"D"，表示出列操作。

    【输出形式】

    若干行，每行一个出列的输出。

    【样例输入】

    3
1
2
3
2
4
D

    【样例输出】

    1

    【样例说明】

    队列中原来有1，2，3三个数，第一个操作使4入列，第二个操作出列，弹出队头的1
    【评分标准】

    通过所有数据

    1. #include 
    2. #include 
    3.  
    4. #define MAX_SIZE 100
    5.  
    6. typedef struct {
    7.     int data[MAX_SIZE];
    8.     int top;
    9. } Stack;
    10.  
    11. void init(Stack *stack) {
    12.     stack->top = -1;
    13. }
    14.  
    15. int isEmpty(Stack *stack) {
    16.     return stack->top == -1;
    17. }
    18.  
    19. int isFull(Stack *stack) {
    20.     return stack->top == MAX_SIZE - 1;
    21. }
    22.  
    23. void push(Stack *stack, int num) {
    24.     if (isFull(stack)) {
    25.         printf("Stack overflow\n");
    26.         return;
    27.     }
    28.     stack->data[++stack->top] = num;
    29. }
    30.  
    31. int pop(Stack *stack) {
    32.     if (isEmpty(stack)) {
    33.         printf("Stack underflow\n");
    34.         return 0;
    35.     }
    36.     return stack->data[stack->top--];
    37. }
    38.  
    39. int main() {
    40.     int n, m;
    41.     scanf("%d", &n);
    42.     Stack s1, s2;
    43.     init(&s1);
    44.     init(&s2);
    45.     int i;
    46.     for (i = 0; i < n; i++) {
    47.         int num;
    48.         scanf("%d", &num);
    49.         push(&s1, num);
    50.     }
    51.     scanf("%d", &m);
    52.     for (i = 0; i < m; i++) {
    53.         char temp_str[2];
    54.         scanf("%s", temp_str);
    55.         if (strcmp(temp_str, "D") == 0) {
    56.             if (isEmpty(&s2)) {
    57.                 while (!isEmpty(&s1)) {
    58.                     int num = pop(&s1);
    59.                     push(&s2, num);
    60.                 }
    61.             }
    62.             int result = pop(&s2);
    63.             printf("%d\n", result);
    64.             n--;
    65.         } else {
    66.             int num = atoi(temp_str);
    67.             push(&s1, num);
    68.             n++;
    69.         }
    70.     }
    71.     return 0;
    72. }

    4. 约瑟夫环

    【问题描述】

    n个人围成一个圈，按顺时针方向一次编号1、2、3、……、n，从第一个人开始顺时针方向依次报数1、2、3、……，报数m的人被淘汰，然后下一个人再从1开始报数，一直重复该过程。由于人数是有限的，因此最后一定只会剩下一个人，求这个人的编号。

    【输入形式】

    第一行，一个整数n，表示约瑟夫环的总人数。

    第二行，一个整数m，表示报到m的人被淘汰。

    【输出形式】

     一行，一个整数，约瑟夫环最终剩下的人的编号。

    【样例输入】

    5
2

    【样例输出】

    3

    【样例说明】

    5个人围成一圈，编号1，2，3，4，5；

    第一轮，2号淘汰，剩下1，3，4，5；

    第二轮，从3开始报数，4号淘汰，剩下1，3，5；

    第三轮，从5开始报数，1号淘汰，剩下3，5；

    第四轮，从3开始报数，5号淘汰，剩下3。
    【评分标准】

    通过所有数据

    1. #include 
    2. #include 
    3.  
    4. typedef struct Node {
    5.     int data;
    6.     struct Node* next;
    7. } Node,*LinkList;
    8.  
    9. LinkList createNode(int data) {
    10.     LinkList newNode = (LinkList)malloc(sizeof(Node));
    11.     newNode->data = data;
    12.     newNode->next = NULL;
    13.     return newNode;
    14. }
    15.  
    16. void appendNode(LinkList* head, int data) {
    17.     LinkList newNode = createNode(data);
    18.     if (*head == NULL) {
    19.         *head = newNode;
    20.         newNode->next = *head;
    21.     } else {
    22.         LinkList temp = *head;
    23.         while (temp->next != *head) {
    24.             temp = temp->next;
    25.         }
    26.         temp->next = newNode;
    27.         newNode->next = *head;
    28.     }
    29. }
    30.  
    31. void deleteNode(LinkList* head, int m) {
    32.     if (*head == NULL) {
    33.         return;
    34.     }
    35.     LinkList current = *head;
    36.     LinkList prev = NULL;
    37.     while (current->next != *head) {
    38.         prev = current;
    39.         current = current->next;
    40.     }
    41.     if (current == *head && current->next == *head) {
    42.         *head = NULL;
    43.         free(current);
    44.         return;
    45.     }
    46.         int i;
    47.         for ( i = 1; i <=m; i++) {
    48.             prev = current;
    49.             current = current->next;
    50.         }
    51.         prev->next = current->next;
    52.         free(current);
    53.         *head = prev->next;
    54. }
    55.  
    56. int josephus(int n, int m) {
    57.     LinkList head = NULL;
    58.     int i;
    59.     for (i = 1; i <= n; i++) {
    60.         appendNode(&head, i);
    61.     }
    62.     while ( head!=head->next) {
    63.         deleteNode(&head, m);
    64.     }
    65.     return head->data;
    66. }
    67.  
    68. int main() {
    69.     int n, m;
    70.     scanf("%d%d", &n, &m);
    71.     int result = josephus(n, m);
    72.     printf("%d\n", result);
    73.     return 0;
    74. }

  • 相关阅读:
    【linux】自定义nameserver
    JS解混淆
    CDN：网站性能的加速器 —— 选择最适合你的CDN服务商
    医院各领域榜单。22个科室、100种常见疾病
    类和对象（上）
    数组和List相互转化（摒弃循环）
    2022.8.2-----leetcode.622
    Mathtype问题汇总
    VR全景广告：让消费者体验沉浸式交互，让营销更有趣
    Vue中事件总线EventBus的应用（三）定义全局事件——实例之main.js-创建事件总线、$emit-发布事件、$on-订阅事件、$off-去除事件
  • 原文地址：https://blog.csdn.net/timberman666/article/details/134016814