栈的应用 - 计算中缀表达式（数据结构与算法 - 计算表达式）

小咪咪 2023-05-21 08:48 1阅读 0赞

本关任务要求通过实现函数double ComputeInfix(char\* s)来计算中缀表达式。

#### 相关知识 ####

中缀表达式的计算需要用到栈。关于链接存储的栈，其中已实现了如下操作：

1.  创建栈：  
    创建一个链式栈。具体操作函数定义如下：

LinkStack* LS_Create()；

1.  释放栈：  
    释放栈所占用的空间。具体操作函数定义如下：

void LS_Free(LinkStack* ls)；

1.  清空一个栈：  
    将链式栈变为空栈。具体操作函数定义如下：

void LS_MakeEmpty(LinkStack* ls)；

1.  判断栈是否为空：  
    若栈为空，则返回true，否则返回false。具体操作函数定义如下：

bool LS_IsEmpty(LinkStack* ls)；

1.  求栈的长度：  
    获取链式栈的长度。具体操作函数定义如下：

int LS_Length(LinkStack* ls)；

1.  将元素 x 进栈：  
    将 x 进栈，若满栈则无法进栈，返回false，否则返回true。具体操作函数定义如下：

void LS_Push(LinkStack* ls, T x)；

1.  出栈：  
    出栈的元素放入item。若出栈成功(栈不为空)，则返回true；否则(空栈)，返回false。具体操作函数定义如下：

bool LS_Pop(LinkStack* ls, T& item)；

1.  获取栈顶元素：  
    获取栈顶元素放入item中。若获取失败(空栈)，则返回false，否则返回true。具体操作函数定义如下：

bool LS_Top(LinkStack* ls, T& item)；

1.  打印栈中元素：  
    从栈顶到栈底打印各结点数据元素。具体操作函数定义如下：

void LS_Print(LinkStack* ls)。

在计算中缀表达式的过程中，你可以根据需要调用以上操作。因为表达式的计算结果可能是浮点数，所以这里将栈的数据元素类型设置为了double类型。

typedef double T;  // 数据元素类型

此外，为了计算中缀表达式，我们定义了如下函数，其中的 1）已经实现，你需要实现 2）：  
1）：

void compute(LinkStack* so, LinkStack* sd);
    /* so为运算符栈 sd为操作数栈 */

该函数处理步骤：  
从运算符栈出栈一个运算符；  
从操作数栈出栈两个操作数；  
用出栈的运算符对出栈的操作数进行运算；  
将运算结果进操作数栈。  
2）：

double ComputeInfix(char* s);
    /* s是中缀表达式符号串，如果表达式是7+8,那么s[0]=’7’,s[1]=’+’,s[2]=’8’。 该函数返回表达式计算结果。 */
    在实现

2）的过程中，可以调用 1）。为了简化你的实现，假设表达式中的操作数都是一个非负`在这里插入代码片`的个位数。后面的测试中，输入数据将符合这一要求。

#include <stdio.h>
    #include <stdlib.h>
    #include "LnkStack.h"
    #include "Infix.h"
    void compute(LinkStack* so, LinkStack* sd)
    //++++++++++++++++++++++++++++++++++++++++++++++
    //so 运算符栈
    //sd 操作数栈
    //1 从运算符栈出栈一个运算符
    //2 从操作数栈出栈两个操作数
    //3 用出栈的运算符对出栈的操作数进行运算
    //4 将运算结果进操作数栈
    //+++++++++++++++++++++++++++++++++++++++++++++++
    { 
        T a,b,c,d;
        LS_Pop(so,c);
        LS_Pop(sd,a);
        LS_Pop(sd,b);
        if (c=='*') 
     { 
      d=b*a; 
     }
        else if (c=='/') 
     { 
      d=b/a;
     }
        else if (c=='+') 
     { 
      d=b+a; 
     }
        else if (c=='-') 
     { 
      d=b-a;
     }
        else 
     { 
      printf("never occur!"); 
     }
        LS_Push(sd, d);
    }
    double ComputeInfix(char* s)
    //计算中缀表达式
    { 
      int i=0;
        LinkStack* so=LS_Create(); // 运算符栈
        LinkStack* sd=LS_Create(); //操作数栈
        while(s[i]) 
     { 
            if ('0'<=s[i] && s[i]<='9') 
      { 
                LS_Push(sd, s[i++]-48);
                continue;
            }
            if(s[i]=='('||LS_IsEmpty(so)) 
      { 
                LS_Push(so, s[i++]); 
                continue;
            }
            if(s[i]==')') 
      { 
                T topitem;
                while(LS_Top(so,topitem) && topitem !='(' ) 
                { 
                 compute(so, sd);
       } 
                LS_Pop(so,topitem);
                i++;
                continue;
            }
            if(s[i]=='*'||s[i]=='/') 
      { 
                T c;
                LS_Top(so,c);
                if (c=='*' || c=='/')
       { 
        compute(so, sd);
        } 
                LS_Push(so, s[i++]);
                continue;
            }
            if(s[i]=='+'||s[i]=='-') 
      { 
                T topitem;
                while(LS_Top(so,topitem) && topitem !='(' ) 
                { 
                 compute(so, sd);
       }
                LS_Push(so, s[i++]);
                continue;
            }
        }
        while(!LS_IsEmpty(so)) 
        { 
         compute(so, sd);
     } 
        T res;
        LS_Top(sd,res);
        LS_Free(so);
        LS_Free(sd);
        return res;
    }