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

【数据结构】【栈（stack）应用】四则运算表达式求值（支持括号、负数）_用计算机实现整数带括号四则运算 数据结构

作者：Monodyee | 2024-05-24 09:13:27

赞

踩

用计算机实现整数带括号四则运算 数据结构

前言：

        先理解原理，再看代码，注意标红字体很重要！结尾附完整测试代码，C语言实现！

更新留言：

        本来是侧重演示栈结构的使用，后面评论区发现很多朋友对这个四则运算比较感兴趣，特此做了更新，新增了对负数的运算支持。

        若您也有新的想法或者需求，请在评论区留言，我将尽可能的实现。需要代码的朋友请直接在章末获取。

        再次感谢您的阅览，谢谢！（更新时间2023年12月05日）

一、四则运算表达式求值

        栈的现实应用也很多，这里重点讲一下比较常见的应用：数学表达式的求值。进入正题之前先讲一下逆波兰的含义。

1.逆波兰（后缀）表达式

        对于“9+(3-1)×3+10÷2”，如果要用后缀表示法应该是什么样子：“9 3 1-3*+102/+”，这样的表达式称为后缀表达式，叫后缀的原因在于所有的符号都是在要运算数字的后面出现。

        请参考下图熟悉一下逆波兰表达式，不需要纠结。

2.后缀表达式计算结果

        计算机如何应用后缀表达式表示“9+(3-1)×3+10÷2”的：

        后缀表达式：9 3 1-3*+10 2/+

        规则：

  • 遍历后缀表达式，如果遇到数字则直接入栈，如果遇到操作符，则弹出栈顶的两个元素，进行计算后将结果入栈。
  • 最终，栈内剩余的元素就是整个表达式的计算结果。

图文演示：

1）初始化一个空栈。此栈用来对要运算的数字进出使用。如下图中左图所示。

2）后缀表达式中前三个都是数字，所以9、3、1进栈。如下图中右图所示。

 3）接下来是“-”，所以将栈中的1出栈作为减数，3出栈作为被减数，并运算3-1得到 2，再将2进栈，如下图中左图所示。

4）接着是数字3进栈，如下图中右图所示。 

5）后面是“*”，也就意味着栈中3和2出栈，2与3相乘，得到6，并将6进栈，如下图中左图所示。

6）下面是“+”，所以栈中6和9出栈，9与6相加，得到15，将15进栈，如下图中右图所示。

7）接着是10与2两数字进栈，如下图中左图所示。

8）接下来是符号“/”，因此，栈顶的2与10出栈，10与2相除，得到5，将5进栈，如下图中右图所示。

 9）最后一个是符号“+”，所以15与5出栈并相加，得到20，将20进栈，如下图中左图所示。

10）结果是20出栈，栈变为空，如下图中右图所示。

注：如果对后缀表达式“9 3 1-3+10 2/+”是怎么出来的？这个问题有疑问的。请继续往下看中缀表达式转后缀表达式。

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

        我们把平时所用的标准四则运算表达式，即“9+(3-1)×3+10÷2”叫做中缀表达式。因为所有的运算符号都在两数字的中间，现在我们的问题就是中缀到后缀的转化。

        中缀表达式“9+(3-1)×3+10÷2”转化为后缀表达式“9 3 1-3*+10 2/+”

规则：

  1. 遇到数字就直接输出到后缀表达式中，遇到操作符就判断其优先级，并将其压入栈中。
  2. 如果栈顶元素的优先级大于等于当前操作符，则先将栈顶元素弹出并输出到后缀表达式中，再将当前操作符压入栈中。
  3. 如果遇到了左括号，则直接将其压入栈中，如果遇到了右括号，则弹出栈中的元素，直到遇到了左括号为止，并将这些元素输出到后缀表达式中。
  4. 最后，将栈中剩余的元素依次弹出，并输出到后缀表达式中。

图文演示：

1）初始化一空栈，用来对符号进出栈使用。如下图的左图所示。

2）第一个字符是数字9，输出9，后面是符号“+”，进栈。如下图的右图所示。

3）第三个字符是“(”，依然是符号，因其只是左括号，还未配对，故进栈。如下图的左图所示。

4）第四个字符是数字3，输出，总表达式为93，接着是“-”，进栈。如下图的右图所示。

5）接下来是数字1，输出，总表达式为 9 31，后面是符号“)”，此时，我们需要去匹配 此前的“(”，所以栈顶依次出栈，并输出，直到“(”出栈为止。此时左括号上方只有“-”， 因此输出“-”。总的输出表达式为 9 3 1-。如下图的左图所示。

6）紧接着是符号“×”，因为此时的栈顶符号为“+”号，优先级低于“×”，因此不输出，“*”进栈。接着是数字3，输出，总的表达式为 9 3 1-3。如下图的右图所示。

7）之后是符号“+”，此时当前栈顶元素“”比这个“+”的优先级高，因此栈中元素出栈并输出（没有比“+”号更低的优先级，所以全部出栈），总输出表达式为9 3 1-3+。然后将当前这个符号“+”进栈。也就是说，前6张图的栈底的“+”是指中缀表达式中开头的9 后面那个“+”，而下图的左图中的栈底（也是栈顶）的“+”是指“9+(3-1)×3+”中的最后 一个“+”。

8）紧接着数字10，输出，总表达式变为9 31-3*+10。后是符号“÷”，所以“/”进栈。如下图的右图所示。

 9）最后一个数字2，输出，总的表达式为9 31-3+10 2。如下图的左图所示。

10）因已经到最后，所以将栈中符号全部出栈并输出。最终输出的后缀表达式结果为 93 1-3+10 2/+。如下图的右图所示。

        从刚才的推导中你会发现，要想让计算机具有处理我们通常的标准（中缀）表达式的能力，最重要的就是两步：

        1.将中缀表达式转化为后缀表达式（栈用来进出运算的符号）。

        2.将后缀表达式进行运算得出结果（栈用来进出运算的数字）。

        整个过程，都充分利用了栈的后进先出特性来处理，理解好它其实也就理解好了栈这个数据结构。

        接下来就是代码实现了。

4.代码实现

        请务必看懂前面两节的内容，思路和原理往往比代码更重要！！！

代码分三部分：

        1）栈结构的构造（C语言实现）

        2）中缀表达式转化为后缀表达式（栈用来进出运算的符号）

        3）后缀表达式进行运算得出结果（栈用来进出运算的数字）

4.1栈结构构造

  1. typedef struct {
  2.     double* data;  // 数组指针
  3.     int top;  // 栈顶指针
  4.     int size;  // 栈的大小
  5. } Stack;
  6.  
  7. // 初始化栈
  8. void initStack(Stack* s, int size) {
  9.     s->data = (double*)malloc(sizeof(double) * size);// 动态分配数组内存
  10.     s->top = -1;
  11.     s->size = size;
  12. }
  13.  
  14. // 判断栈是否为空
  15. int isEmpty(Stack* s) {
  16.     return s->top == -1;
  17. }
  18.  
  19. // 判断栈是否已满
  20. int isFull(Stack* s) {
  21.     return s->top == s->size - 1;
  22. }
  23.  
  24. // 入栈
  25. void push(Stack* s, double value) {
  26.     if (isFull(s)) { // 检查栈是否已满
  27.         printf("Stack overflow\n");
  28.         exit(1); // 若栈已满，则退出程序
  29.     }
  30.  
  31.     s->top++; // 栈顶指针加1
  32.     s->data[s->top] = value; // 在栈顶插入新值
  33. }
  34.  
  35. // 出栈
  36. double pop(Stack* s) {
  37.     if (isEmpty(s)) { // 检查栈是否为空
  38.         printf("Stack underflow\n");
  39.         exit(1); // 若栈为空，则退出程序
  40.     }
  41.  
  42.     double value = s->data[s->top]; // 储存栈顶元素的值
  43.     s->top--; // 栈顶指针减1
  44.     return value; // 返回栈顶元素的值
  45. }
  46.  
  47. // 获取栈顶元素
  48. double top(Stack* s) {
  49.     if (isEmpty(s)) { // 检查栈是否为空
  50.         printf("Stack underflow\n");
  51.         exit(1); // 若栈为空，则退出程序
  52.     }
  53.  
  54.     return s->data[s->top]; // 返回栈顶元素的值
  55. }

4.2将中缀转换成后缀

  1. // 将中缀表达式转换成后缀表达式
  2. void infixToPostfix(char* infix, char* postfix) {
  3.     Stack s;
  4.     initStack(&s, 100);// 初始化栈
  5.  
  6.     char* p = infix;// 使用指针遍历中缀表达式
  7.     char* q = postfix;// 使用指针储存后缀表达式
  8.     while (*p != '\0') {// 如果当前位置不为空
  9.         if (isdigit(*p)) {// 如果当前位置是数字
  10.             while (isdigit(*p) || *p == '.') {
  11.                 *q = *p;// 直接输出
  12.                 q++;
  13.                 p++;
  14.             }
  15.             *q = ' ';
  16.             q++;
  17.         }
  18.         else if (*p == '+' || *p == '-' || *p == '*' || *p == '/') {// 如果当前位置是运算符
  19.             int priority1 = getPriority(*p);// 获取当前运算符的优先级
  20.             while (!isEmpty(&s) && isOperator(top(&s)) && getPriority(top(&s)) >= priority1) {
  21.                 // 如果栈不空，栈顶为运算符，并且栈顶运算符的优先级大于等于当前运算符的优先级
  22.                 char op = pop(&s);// 将栈顶运算符弹出
  23.                 *q = op;// 将弹出的运算符输出到后缀表达式中
  24.                 q++;
  25.                 *q = ' ';// 输出空格
  26.                 q++;
  27.             }
  28.             push(&s, *p);// 将当前运算符入栈
  29.             p++;
  30.         }
  31.         else if (*p == '(') {// 如果当前位置是左括号
  32.             push(&s, *p);// 将其入栈
  33.             p++;
  34.         }
  35.         else if (*p == ')') {// 如果当前位置是右括号
  36.             while (!isEmpty(&s) && top(&s) != '(') {// 不断将栈中的元素弹出，直到遇到左括号
  37.                 char op = pop(&s);
  38.                 *q = op;// 将弹出的运算符输出到后缀表达式中
  39.                 q++;
  40.                 *q = ' ';// 输出空格
  41.                 q++;
  42.             }
  43.             if (!isEmpty(&s) && top(&s) == '(') {// 如果栈不空且栈顶元素是左括号
  44.                 pop(&s);// 将左括号弹出并丢弃
  45.             }
  46.             else {
  47.                 printf("Invalid expression: %s\n", infix);// 若遍历完中缀表达式后栈中仍然有元素，或遇到错误情况，则输出错误信息
  48.                 exit(1);
  49.             }
  50.             p++;
  51.         }
  52.         else {// 如果当前位置不是数字、运算符、左括号或右括号，直接跳过
  53.             p++;
  54.         }
  55.     }
  56.  
  57.     while (!isEmpty(&s)) {// 如果栈不空，则将栈中所有元素弹出并输出到后缀表达式中
  58.         char op = pop(&s);
  59.         *q = op;
  60.         q++;
  61.         *q = ' ';// 输出空格
  62.         q++;
  63.     }
  64.  
  65.     *(q - 1) = '\0';// 给后缀表达式添加结束符
  66. }

4.3计算后缀表达式的值

  1. // 计算后缀表达式的值
  2. double evaluate(char* postfix) {
  3.     Stack s;
  4.     initStack(&s, 100);// 初始化栈
  5.  
  6.     char* p = postfix;// 使用指针遍历后缀表达式
  7.     while (*p != '\0') {// 如果当前位置不为空
  8.         if (isdigit(*p)) {// 如果当前位置是数字
  9.             double num = *p - '0';// 获取数字的整数部分
  10.             p++;
  11.             while (isdigit(*p) || *p == '.') {// 继续读取小数部分
  12.                 if (*p == '.') {    // 如果当前位置是小数点
  13.                     p++;
  14.                     double frac = 0.1;// 初始化分数
  15.                     while (isdigit(*p)) {// 继续读取小数部分
  16.                         num += (*p - '0') * frac;// 计算小数值
  17.                         p++;
  18.                         frac /= 10;// 分数部分减小
  19.                     }
  20.                     break;  // 跳出读取小数值的循环
  21.                 }
  22.                 else {// 如果不是小数点，表示当前位置是数字
  23.                     num = num * 10 + (*p - '0');// 计算数字值
  24.                     p++;
  25.                 }
  26.             }
  27.             push(&s, num);// 将数字入栈
  28.         }
  29.         else if (*p == '+' || *p == '-' || *p == '*' || *p == '/') {// 如果当前位置是运算符
  30.             double num2 = pop(&s);// 从栈中弹出栈顶元素作为第二个操作数
  31.             double num1 = pop(&s);// 再从栈中弹出栈顶元素作为第一个操作数
  32.             double result = operate(num1, num2, *p);// 利用operate函数计算出结果
  33.             push(&s, result);// 将结果压入栈中
  34.             p++;
  35.         }
  36.         else {
  37.             p++;
  38.         }
  39.     }
  40.  
  41.     double value = pop(&s);
  42.     return value;// 返回栈顶元素，即为最终结果
  43. }

完整测试代码：

  1. #define _CRT_SECURE_NO_WARNINGS 1
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. #include <ctype.h>
  5.  
  6. typedef struct {
  7.     double* data;  // 数组指针
  8.     int top;  // 栈顶指针
  9.     int size;  // 栈的大小
  10. } Stack;
  11.  
  12. // 初始化栈
  13. void initStack(Stack* s, int size) {
  14.     s->data = (double*)malloc(sizeof(double) * size);// 动态分配数组内存
  15.     s->top = -1;
  16.     s->size = size;
  17. }
  18.  
  19. // 判断栈是否为空
  20. int isEmpty(Stack* s) {
  21.     return s->top == -1;
  22. }
  23.  
  24. // 判断栈是否已满
  25. int isFull(Stack* s) {
  26.     return s->top == s->size - 1;
  27. }
  28.  
  29. // 入栈
  30. void push(Stack* s, double value) {
  31.     if (isFull(s)) { // 检查栈是否已满
  32.         printf("Stack overflow\n");
  33.         exit(1); // 若栈已满，则退出程序
  34.     }
  35.  
  36.     s->top++; // 栈顶指针加1
  37.     s->data[s->top] = value; // 在栈顶插入新值
  38. }
  39.  
  40. // 出栈
  41. double pop(Stack* s) {
  42.     if (isEmpty(s)) { // 检查栈是否为空
  43.         printf("Stack underflow\n");
  44.         exit(1); // 若栈为空，则退出程序
  45.     }
  46.  
  47.     double value = s->data[s->top]; // 储存栈顶元素的值
  48.     s->top--; // 栈顶指针减1
  49.     return value; // 返回栈顶元素的值
  50. }
  51.  
  52. // 获取栈顶元素
  53. double top(Stack* s) {
  54.     if (isEmpty(s)) { // 检查栈是否为空
  55.         printf("Stack underflow\n");
  56.         exit(1); // 若栈为空，则退出程序
  57.     }
  58.  
  59.     return s->data[s->top]; // 返回栈顶元素的值
  60. }
  61.  
  62. // 判断是否为运算符
  63. int isOperator(char c) {
  64.     return c == '+' || c == '-' || c == '*' || c == '/';
  65. }
  66.  
  67. // 获取运算符优先级
  68. int getPriority(char op) {
  69.     switch (op) {
  70.     case '+':
  71.     case '-':
  72.         return 1;
  73.     case '*':
  74.     case '/':
  75.         return 2;
  76.     default:
  77.         return 0;
  78.     }
  79. }
  80.  
  81. // 四则运算
  82. double operate(double num1, double num2, char op) {
  83.     switch (op) {
  84.     case '+':
  85.         return num1 + num2;
  86.     case '-':
  87.         return num1 - num2;
  88.     case '*':
  89.         return num1 * num2;
  90.     case '/':
  91.         return num1 / num2;
  92.     default:
  93.         printf("Invalid operator: %c\n", op);
  94.         exit(1);
  95.     }
  96. }
  97.  
  98. // 计算后缀表达式的值
  99. double evaluate(char* postfix) {
  100.     Stack s;
  101.     initStack(&s, 100);// 初始化栈
  102.  
  103.     char* p = postfix;// 使用指针遍历后缀表达式
  104.     while (*p != '\0') {// 如果当前位置不为空
  105.         if (isdigit(*p)) {// 如果当前位置是数字
  106.             double num = *p - '0';// 获取数字的整数部分
  107.             p++;
  108.             while (isdigit(*p) || *p == '.') {// 继续读取小数部分
  109.                 if (*p == '.') {    // 如果当前位置是小数点
  110.                     p++;
  111.                     double frac = 0.1;// 初始化分数
  112.                     while (isdigit(*p)) {// 继续读取小数部分
  113.                         num += (*p - '0') * frac;// 计算小数值
  114.                         p++;
  115.                         frac /= 10;// 分数部分减小
  116.                     }
  117.                     break;  // 跳出读取小数值的循环
  118.                 }
  119.                 else {// 如果不是小数点，表示当前位置是数字
  120.                     num = num * 10 + (*p - '0');// 计算数字值
  121.                     p++;
  122.                 }
  123.             }
  124.             push(&s, num);// 将数字入栈
  125.         }
  126.         else if (*p == '+' || *p == '-' || *p == '*' || *p == '/') {// 如果当前位置是运算符
  127.             double num2 = pop(&s);// 从栈中弹出栈顶元素作为第二个操作数
  128.             double num1 = pop(&s);// 再从栈中弹出栈顶元素作为第一个操作数
  129.             double result = operate(num1, num2, *p);// 利用operate函数计算出结果
  130.             push(&s, result);// 将结果压入栈中
  131.             p++;
  132.         }
  133.         else {
  134.             p++;
  135.         }
  136.     }
  137.  
  138.     double value = pop(&s);
  139.     return value;// 返回栈顶元素，即为最终结果
  140. }
  141.  
  142. // 将中缀表达式转换成后缀表达式
  143. void infixToPostfix(char* infix, char* postfix) {
  144.     Stack s;
  145.     initStack(&s, 100);// 初始化栈
  146.  
  147.     char* p = infix;// 使用指针遍历中缀表达式
  148.     char* q = postfix;// 使用指针储存后缀表达式
  149.     while (*p != '\0') {// 如果当前位置不为空
  150.         if (isdigit(*p)) {// 如果当前位置是数字
  151.             while (isdigit(*p) || *p == '.') {
  152.                 *q = *p;// 直接输出
  153.                 q++;
  154.                 p++;
  155.             }
  156.             *q = ' ';
  157.             q++;
  158.         }
  159.         else if (*p == '+' || *p == '-' || *p == '*' || *p == '/') {// 如果当前位置是运算符
  160.             int priority1 = getPriority(*p);// 获取当前运算符的优先级
  161.             while (!isEmpty(&s) && isOperator(top(&s)) && getPriority(top(&s)) >= priority1) {
  162.                 // 如果栈不空，栈顶为运算符，并且栈顶运算符的优先级大于等于当前运算符的优先级
  163.                 char op = pop(&s);// 将栈顶运算符弹出
  164.                 *q = op;// 将弹出的运算符输出到后缀表达式中
  165.                 q++;
  166.                 *q = ' ';// 输出空格
  167.                 q++;
  168.             }
  169.             push(&s, *p);// 将当前运算符入栈
  170.             p++;
  171.         }
  172.         else if (*p == '(') {// 如果当前位置是左括号
  173.             push(&s, *p);// 将其入栈
  174.             p++;
  175.         }
  176.         else if (*p == ')') {// 如果当前位置是右括号
  177.             while (!isEmpty(&s) && top(&s) != '(') {// 不断将栈中的元素弹出，直到遇到左括号
  178.                 char op = pop(&s);
  179.                 *q = op;// 将弹出的运算符输出到后缀表达式中
  180.                 q++;
  181.                 *q = ' ';// 输出空格
  182.                 q++;
  183.             }
  184.             if (!isEmpty(&s) && top(&s) == '(') {// 如果栈不空且栈顶元素是左括号
  185.                 pop(&s);// 将左括号弹出并丢弃
  186.             }
  187.             else {
  188.                 printf("Invalid expression: %s\n", infix);// 若遍历完中缀表达式后栈中仍然有元素，或遇到错误情况，则输出错误信息
  189.                 exit(1);
  190.             }
  191.             p++;
  192.         }
  193.         else {// 如果当前位置不是数字、运算符、左括号或右括号，直接跳过
  194.             p++;
  195.         }
  196.     }
  197.  
  198.     while (!isEmpty(&s)) {// 如果栈不空，则将栈中所有元素弹出并输出到后缀表达式中
  199.         char op = pop(&s);
  200.         *q = op;
  201.         q++;
  202.         *q = ' ';// 输出空格
  203.         q++;
  204.     }
  205.  
  206.     *(q - 1) = '\0';// 给后缀表达式添加结束符
  207. }
  208.  
  209.  
  210. int main() {
  211.     char infix[100];
  212.     char postfix[100];
  213.  
  214.     printf("Enter an infix expression: ");
  215.     scanf("%s", infix);
  216.  
  217.     infixToPostfix(infix, postfix);// 将中缀表达式转为后缀表达式
  218.     printf("Postfix notation: %s\n", postfix);
  219.  
  220.     double result = evaluate(postfix);// 计算后缀表达式的值
  221.     printf("Result: %g\n", result);
  222.  
  223.     return 0;
  224. }
  225.

测试结果： 

更新测试代码： 支持负数运算

  1. #define _CRT_SECURE_NO_WARNINGS 1
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. #include <ctype.h>
  5.  
  6. typedef struct {
  7.     double* data;  // 存储栈数据的数组指针
  8.     int top;       // 栈顶指针
  9.     int size;      // 栈的大小
  10. } Stack;
  11.  
  12. // 初始化栈
  13. void initStack(Stack* s, int size) {
  14.     s->data = (double*)malloc(sizeof(double) * size); // 动态分配内存
  15.     s->top = -1; // 初始化栈顶指针
  16.     s->size = size; // 设置栈的大小
  17. }
  18.  
  19. // 判断栈是否为空
  20. int isEmpty(Stack* s) {
  21.     return s->top == -1; // 栈顶指针为-1时，栈为空
  22. }
  23.  
  24. // 判断栈是否已满
  25. int isFull(Stack* s) {
  26.     return s->top == s->size - 1; // 栈顶指针等于栈的大小减1时，栈已满
  27. }
  28.  
  29. // 入栈操作
  30. void push(Stack* s, double value) {
  31.     if (isFull(s)) {
  32.         printf("Stack overflow\n");
  33.         exit(1); // 栈满时退出程序
  34.     }
  35.     s->top++; // 栈顶指针增加
  36.     s->data[s->top] = value; // 将值放入栈顶
  37. }
  38.  
  39. // 出栈操作
  40. double pop(Stack* s) {
  41.     if (isEmpty(s)) {
  42.         printf("Stack underflow\n");
  43.         exit(1); // 栈空时退出程序
  44.     }
  45.     double value = s->data[s->top]; // 取栈顶元素
  46.     s->top--; // 栈顶指针减少
  47.     return value; // 返回栈顶元素
  48. }
  49.  
  50. // 获取栈顶元素
  51. double top(Stack* s) {
  52.     if (isEmpty(s)) {
  53.         printf("Stack underflow\n");
  54.         exit(1); // 栈空时退出程序
  55.     }
  56.     return s->data[s->top]; // 返回栈顶元素
  57. }
  58.  
  59. // 判断字符是否是运算符
  60. int isOperator(char c) {
  61.     return c == '+' || c == '-' || c == '*' || c == '/';
  62. }
  63.  
  64. // 获取运算符优先级
  65. int getPriority(char op) {
  66.     switch (op) {
  67.     case '+':
  68.     case '-':
  69.         return 1;
  70.     case '*':
  71.     case '/':
  72.         return 2;
  73.     default:
  74.         return 0;
  75.     }
  76. }
  77.  
  78. // 执行四则运算
  79. double operate(double num1, double num2, char op) {
  80.     switch (op) {
  81.     case '+':
  82.         return num1 + num2;
  83.     case '-':
  84.         return num1 - num2;
  85.     case '*':
  86.         return num1 * num2;
  87.     case '/':
  88.         return num1 / num2;
  89.     default:
  90.         printf("Invalid operator: %c\n", op);
  91.         exit(1); // 遇到无效运算符时退出程序
  92.     }
  93. }
  94.  
  95. // 判断是否是负号
  96. int isNegativeSign(char* p, char* infix) {
  97.     if (*p != '-') return 0; // 如果不是减号，则返回0
  98.     if (p == infix) return 1; // 如果是表达式的开始，则是负号
  99.     // 如果前一个字符是左括号或其他运算符，则当前的减号是负号
  100.     return (*(p - 1) == '(') || isOperator(*(p - 1));
  101. }
  102.  
  103. // 将中缀表达式转换为后缀表达式
  104. void infixToPostfix(char* infix, char* postfix) {
  105.     Stack s;
  106.     initStack(&s, 100); // 初始化栈
  107.  
  108.     char* p = infix;
  109.     char* q = postfix;
  110.     while (*p != '\0') {
  111.         if (isdigit(*p)) { // 如果是数字
  112.             do {
  113.                 *q++ = *p++;
  114.             } while (isdigit(*p) || *p == '.');
  115.             *q++ = ' ';
  116.         } else if (isOperator(*p)) {
  117.             if (*p == '-' && isNegativeSign(p, infix)) {
  118.                 *q++ = '0'; // 补零以处理负号
  119.                 *q++ = ' ';
  120.             }
  121.             while (!isEmpty(&s) && isOperator(top(&s)) &&
  122.                    getPriority(top(&s)) >= getPriority(*p)) {
  123.                 *q++ = pop(&s);
  124.                 *q++ = ' ';
  125.             }
  126.             push(&s, *p);
  127.             p++;
  128.         } else if (*p == '(') {
  129.             push(&s, *p); // 处理左括号
  130.             p++;
  131.         } else if (*p == ')') {
  132.             while (!isEmpty(&s) && top(&s) != '(') {
  133.                 *q++ = pop(&s); // 处理右括号
  134.                 *q++ = ' ';
  135.             }
  136.             if (!isEmpty(&s)) {
  137.                 pop(&s); // 弹出左括号
  138.             }
  139.             p++;
  140.         } else {
  141.             p++; // 跳过空格
  142.         }
  143.     }
  144.  
  145.     while (!isEmpty(&s)) { // 将栈中剩余的运算符加入后缀表达式
  146.         *q++ = pop(&s);
  147.         *q++ = ' ';
  148.     }
  149.  
  150.     *q = '\0'; // 结束后缀表达式
  151. }
  152.  
  153. // 计算后缀表达式的值
  154. double evaluate(char* postfix) {
  155.     Stack s;
  156.     initStack(&s, 100); // 初始化栈
  157.  
  158.     char* p = postfix;
  159.     while (*p != '\0') {
  160.         if (isdigit(*p)) { // 如果是数字
  161.             double num = 0.0;
  162.             while (isdigit(*p)) { // 提取整数部分
  163.                 num = num * 10 + (*p - '0');
  164.                 p++;
  165.             }
  166.             if (*p == '.') { // 提取小数部分
  167.                 double frac = 0.1;
  168.                 p++;
  169.                 while (isdigit(*p)) {
  170.                     num += (*p - '0') * frac;
  171.                     frac /= 10;
  172.                     p++;
  173.                 }
  174.             }
  175.             push(&s, num);
  176.         } else if (*p == ' ') {
  177.             p++;
  178.         } else if (isOperator(*p)) { // 如果是运算符
  179.             double num2 = pop(&s);
  180.             double num1 = pop(&s);
  181.             double result = operate(num1, num2, *p);
  182.             push(&s, result);
  183.             p++;
  184.         }
  185.     }
  186.  
  187.     return pop(&s); // 返回计算结果
  188. }
  189.  
  190. int main() {
  191.     char infix[100];
  192.     char postfix[100];
  193.  
  194.     printf("Enter an infix expression: ");
  195.     scanf("%s", infix); // 读取中缀表达式
  196.  
  197.     infixToPostfix(infix, postfix); // 将中缀表达式转换为后缀表达式
  198.     printf("Postfix notation: %s\n", postfix); // 打印后缀表达式
  199.  
  200.     double result = evaluate(postfix); // 计算后缀表达式的结果
  201.     printf("Result: %g\n", result); // 打印结果
  202.  
  203.     return 0;
  204. }

 测试截图：

参考：

  1. 石田保辉：《我的第一本算法书》
  2. 渡部有隆：《挑战程序设计竞赛2》
  3. 程杰：《大话数据结构》
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Monodyee/article/detail/616761
推荐阅读
相关标签

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

  

闽ICP备14008679号