devbox
一键难忘520
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

数据结构实训：表达式求值器（非常详细）_表达式求值器问题描述:设计一个表达式求值器,能够解析和计算由数字、运算符和括号

作者：一键难忘520 | 2024-06-29 21:41:17

赞

踩

表达式求值器问题描述:设计一个表达式求值器,能够解析和计算由数字、运算符和括号

表达式求值器

问题描述：

设计一个表达式求值器，能够解析和计算由数字、运算符和括号组成的算术表达式。要求实现基本的四则运算，如加、减、乘、除，并处理运算符的优先级和括号。

设计要点：

1. 使用栈作为数据结构来处理运算符和操作数的优先级。

2. 实现表达式的解析算法，将输入的字符串转换为内部表示形式，如逆波兰表示法。

3. 设计求值算法，根据运算符的优先级和操作数的顺序进行计算。

完整代码（超详细）

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <ctype.h>
  4. #include <string.h>
  5.  
  6. #define MAX 100
  7.  
  8. typedef struct {
  9.     int top;
  10.     char items[MAX];
  11. } Stack;
  12.  
  13. void initStack(Stack* s) {
  14.     s->top = -1;
  15. }
  16.  
  17. int isEmpty(Stack* s) {
  18.     return (s->top == -1);
  19. }
  20.  
  21. int isFull(Stack* s) {
  22.     return (s->top == MAX - 1);
  23. }
  24.  
  25. void push(Stack* s, char value) {
  26.     if (!isFull(s)) {
  27.         s->items[++(s->top)] = value;
  28.     }
  29.     else {
  30.         printf("栈满了\n");
  31.     }
  32. }
  33.  
  34. char pop(Stack* s) {
  35.     if (!isEmpty(s)) {
  36.         return s->items[(s->top)--];
  37.     }
  38.     else {
  39.         printf("栈为空\n");
  40.         return 0;
  41.     }
  42. }
  43.  
  44. char peek(Stack* s) {
  45.     if (!isEmpty(s)) {
  46.         return s->items[s->top];
  47.     }
  48.     else {
  49.         return '\0';
  50.     }
  51. }
  52.  
  53. int precedence(char op) {
  54.     switch (op) {
  55.     case '+':
  56.     case '-':
  57.         return 1;
  58.     case '*':
  59.     case '/':
  60.         return 2;
  61.     default:
  62.         return 0;
  63.     }
  64. }
  65.  
  66. int isOperator(char ch) {
  67.     return (ch == '+' || ch == '-' || ch == '*' || ch == '/');
  68. }
  69.  
  70. void infixToPostfix(char* infix, char* postfix) {
  71.     Stack s;
  72.     initStack(&s);
  73.     int k = 0;
  74.  
  75.     for (int i = 0; infix[i] != '\0'; i++) {
  76.         if (isdigit(infix[i])) {
  77.             while (isdigit(infix[i])) {
  78.                 postfix[k++] = infix[i++];
  79.             }
  80.             postfix[k++] = ' ';
  81.             i--;
  82.         }
  83.         else if (infix[i] == '(') {
  84.             push(&s, infix[i]);
  85.         }
  86.         else if (infix[i] == ')') {
  87.             while (!isEmpty(&s) && peek(&s) != '(') {
  88.                 postfix[k++] = pop(&s);
  89.                 postfix[k++] = ' ';
  90.             }
  91.             pop(&s); 
  92.         }
  93.         else if (isOperator(infix[i])) {
  94.             while (!isEmpty(&s) && precedence(peek(&s)) >= precedence(infix[i])) {
  95.                 postfix[k++] = pop(&s);
  96.                 postfix[k++] = ' ';
  97.             }
  98.             push(&s, infix[i]);
  99.         }
  100.     }
  101.  
  102.     while (!isEmpty(&s)) {
  103.         postfix[k++] = pop(&s);
  104.         postfix[k++] = ' ';
  105.     }
  106.     postfix[k - 1] = '\0'; 
  107. }
  108.  
  109. int evaluatePostfix(char* postfix) {
  110.     Stack s;
  111.     initStack(&s);
  112.     int i = 0;
  113.     while (postfix[i] != '\0') {
  114.         if (isdigit(postfix[i])) {
  115.             int num = 0;
  116.             while (isdigit(postfix[i])) {
  117.                 num = num * 10 + (postfix[i++] - '0');
  118.             }
  119.             push(&s, num);
  120.         }
  121.         else if (isOperator(postfix[i])) {
  122.             int val2 = pop(&s);
  123.             int val1 = pop(&s);
  124.             switch (postfix[i]) {
  125.             case '+': push(&s, val1 + val2); break;
  126.             case '-': push(&s, val1 - val2); break;
  127.             case '*': push(&s, val1 * val2); break;
  128.             case '/': push(&s, val1 / val2); break;
  129.             }
  130.             i++;
  131.         }
  132.         else {
  133.             i++;
  134.         }
  135.     }
  136.     return pop(&s);
  137. }
  138.  
  139. int main() {
  140.     char infix[MAX], postfix[MAX];
  141.     printf("Enter an infix expression: ");
  142.     fgets(infix, MAX, stdin);
  143.     infix[strcspn(infix, "\n")] = '\0'; 
  144.  
  145.     infixToPostfix(infix, postfix);
  146.     printf("Postfix expression: %s\n", postfix);
  147.  
  148.     int result = evaluatePostfix(postfix);
  149.     printf("Result: %d\n", result);
  150.  
  151.     return 0;
  152. }

代码解释（主要看这个） 

 1.栈的实现

 typedef struct {

int top;

char items[MAX];

} Stack;

这里定义了一个结构体 Stack，它包含一个整数 top 用于指示栈顶位置，以及一个字符数组 items 作为栈的存储空间。

  • initStack: 初始化栈，将 top 设置为 -1 表示栈为空。
  • isEmpty: 检查栈是否为空。
  • isFull: 检查栈是否已满。
  • push: 入栈操作，如果栈未满，将元素压入栈顶。
  • pop: 出栈操作，如果栈非空，弹出并返回栈顶元素。
  • peek: 查看栈顶元素，但不移除。

 2. 运算符优先级和判断

int precedence(char op) {
    switch (op) {
        case '+':
        case '-':
            return 1;
        case '*':
        case '/':
            return 2;
        default:
            return 0;
    }
}

int isOperator(char ch) {
    return (ch == '+' || ch == '-' || ch == '*' || ch == '/');
}

  • precedence: 返回运算符的优先级，+ 和 - 优先级较低（返回1），* 和 / 优先级较高（返回2），其他情况返回0。
  • isOperator: 判断字符是否为运算符。

3. 中缀转后缀表达式

void infixToPostfix(char* infix, char* postfix) {
    Stack s;
    initStack(&s);
    int k = 0;

    for (int i = 0; infix[i] != '\0'; i++) {
        if (isdigit(infix[i])) {
            while (isdigit(infix[i])) {
                postfix[k++] = infix[i++];
            }
            postfix[k++] = ' '; // 添加空格作为后缀表达式元素的分隔符
            i--; // 退回到数字的最后一个字符
        } else if (infix[i] == '(') {
            push(&s, infix[i]);
        } else if (infix[i] == ')') {
            while (!isEmpty(&s) && peek(&s) != '(') {
                postfix[k++] = pop(&s);
                postfix[k++] = ' ';
            }
            pop(&s); // 弹出 '('
        } else if (isOperator(infix[i])) {
            while (!isEmpty(&s) && precedence(peek(&s)) >= precedence(infix[i])) {
                postfix[k++] = pop(&s);
                postfix[k++] = ' ';
            }
            push(&s, infix[i]);
        }
    }

    // 将栈中剩余的运算符弹出并添加到后缀表达式中
    while (!isEmpty(&s)) {
        postfix[k++] = pop(&s);
        postfix[k++] = ' ';
    }
    postfix[k-1] = '\0'; // 移除最后一个空格，并添加字符串结束符
}

  • infixToPostfix: 将中缀表达式转换为后缀表达式。遍历中缀表达式，根据操作数、运算符和括号进行处理，并使用栈来管理运算符的顺序。

4. 后缀表达式求值

int evaluatePostfix(char* postfix) {
    Stack s;
    initStack(&s);
    int i = 0;
    while (postfix[i] != '\0') {
        if (isdigit(postfix[i])) {
            int num = 0;
            while (isdigit(postfix[i])) {

//这段代码用于解析并提取后缀表达式（即逆波兰表达式）中的数字
                num = num * 10 + (postfix[i++] - '0');

            }
            push(&s, num);
        } else if (isOperator(postfix[i])) {
            int val2 = pop(&s);
            int val1 = pop(&s);
            switch (postfix[i]) {
                case '+': push(&s, val1 + val2); break;
                case '-': push(&s, val1 - val2); break;
                case '*': push(&s, val1 * val2); break;
                case '/': push(&s, val1 / val2); break;
            }
            i++;
        } else {
            i++; // 跳过空格
        }
    }
    return pop(&s); // 返回最终的计算结果
}

num = num * 10 + (postfix[i++] - '0');详细解释

  1. isdigit(postfix[i]):

    • isdigit 是一个标准库函数，用于检查给定字符是否为数字字符（'0' 到 '9'）。如果 postfix[i] 是数字字符，则返回非零值，否则返回零。
    • postfix[i] 是当前正在处理的字符。

  2. num = num * 10 + (postfix[i++] - '0');:

    • num 是用来存储最终解析出的整数的变量。
    • postfix[i++] - '0'：
      • postfix[i] 是当前的数字字符。
      • 减去字符 '0' 将字符转换为对应的整数值。例如，字符 '7' 减去 '0' 的 ASCII 值等于整数 7。
      • i++ 是后置递增操作，表示在使用 postfix[i] 之后，再将 i 增加 1，以便指向下一个字符。
    • num = num * 10 + ...：
      • 每次循环中，将新的数字字符与之前解析的部分组合起来。
      • 例如，如果之前 num 是 12，现在读取到一个新的数字字符 '3'，那么计算 num = 12 * 10 + 3 结果为 123。

  • evaluatePostfix: 对后缀表达式进行求值。遍历后缀表达式，遇到操作数则压入栈中，遇到运算符则弹出栈顶的两个操作数进行运算，并将结果压回栈中，直到表达式结束。

 5. 主函数

int main() {
    char infix[MAX], postfix[MAX];
    printf("Enter an infix expression: ");
    fgets(infix, MAX, stdin);
    infix[strcspn(infix, "\n")] = '\0'; // 去除末尾的换行符

    infixToPostfix(infix, postfix);
    printf("Postfix expression: %s\n", postfix);

    int result = evaluatePostfix(postfix);
    printf("Result: %d\n", result);

    return 0;
}

  • 主函数负责接收用户输入的中缀表达式，调用 infixToPostfix 转换为后缀表达式，然后调用 evaluatePostfix 计算结果并输出。

这些代码组合在一起实现了一个基本的表达式求值器，仅可以处理加减乘除四则运算和括号。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/一键难忘520/article/detail/770399
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号