数据结构--栈和队列及应用--表达式求值

柔光的暖阳◎ 2023-07-03 14:26 15阅读 0赞

# 数据结构–栈和队列及应用–表达式求值 #

## 【实验目的】 ##

使学生深入了解栈和队列的特性，以便在实际问题背景下灵活运用它们，同时还将巩固对这两个结构的构造方法的掌握及基本操作的实现。

## 【实验内容及要求】 ##

１、问题描述：实现表达式求值。算法输入为表达式字符串，输出为该表达式的计算结果。要求表达式字符串支持正整数类型的操作数，支持+，-，*，/四种算数运算符，支持若干函数运算符。比如，exp(x)表示 ，log10(x)表示 ，sqrt(x)表示 。试计算3*(sqrt(7-5)/2)的值。  
２、基本要求：实现如下要求（1）-（3）。如果只实现要求（1）-（2），成绩为80。  
（1）首先实现栈的基本操作，如入栈、出栈、取栈顶元素等。栈的实现不能使用编译环境中的库函数。  
（2）实现支持+，-，*，/四种算数运算符的表达式求值。  
（3）在（2）的基础上扩展支持函数运算符。  
3、实现提示：假设表达式字符串是“\# … a β b θ c … \#”，其中β 和 θ是运算符，a、b、c是操作数，下面是运算符优先级关系表（加入了exp(x)函数），其他函数请自行加入。![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dYX3RpbWk_size_16_color_FFFFFF_t_70]  
词法分析方法提示：假设表达式串为S，从当前位置i开始计算，首先得到最靠近i的运算符（包括函数）所在的位置j，如果j>i，则意味着S\[i…j-1\]是操作数；如果j=0，则意味着S\[i…\]是操作数。例如，对于表达式串S=”30*sqrt(70-50)”，最左端的运算符是\*，其位置为2，因此操作数为S\[0…1\]=”30”。

## 【实验数据】 ##

#include <iostream>
    #include"stdio.h"
    #include"stdlib.h"
    #include"string.h"
    #include"math.h"
    #define true 1
    #define false 0
    #define OK 1
    #define OPSETSIZE 8
    using namespace std;
    typedef int Status;
    
    unsigned char Prior[8][8] =
    {
        
        // 运算符优先级表
        //     '+' '-' '*' '/' '(' ')' '#' '^'
        /*'+'*/'>','>','<','<','<','>','>','<',
        /*'-'*/'>','>','<','<','<','>','>','<',
        /*'*'*/'>','>','>','>','<','>','>','<',
        /*'/'*/'>','>','>','>','<','>','>','<',
        /*'('*/'<','<','<','<','<','=',' ','<',
        /*')'*/'>','>','>','>',' ','>','>','>',
        /*'#'*/'<','<','<','<','<',' ','=','<',
        /*'^'*/'>','>','>','>','<','>','>','>',
    };
    
    typedef struct StackChar
    {
        
        char c;
        struct StackChar *next;
    } SC;      //StackChar类型的结点SC
    
    typedef struct StackFloat
    {
        
        float f;
        struct StackFloat *next;
    } SF;      //StackFloat类型的结点SF
    
    SC *Push(SC *s,char c)          //SC类型的指针Push，返回p
    {
        
        SC *p=(SC*)malloc(sizeof(SC));
        p->c=c;
        p->next=s;
        return p;
    }
    
    SF *Push(SF *s,float f)        //SF类型的指针Push，返回p
    {
        
        SF *p=(SF*)malloc(sizeof(SF));
        p->f=f;
        p->next=s;
        return p;
    }
    
    SC *Pop(SC *s)    //SC类型的指针Pop
    {
        
        SC *q=s;
        s=s->next;
        free(q);
        return s;
    }
    
    SF *Pop(SF *s)      //SF类型的指针Pop
    {
        
        SF *q=s;
        s=s->next;
        free(q);
        return s;
    }
    
    float Operate(float a,unsigned char theta, float b)      //计算函数Operate
    {
        
        switch(theta)
        {
        
        case '+':
            return a+b;
        case '-':
            return a-b;
        case '*':
            return a*b;
        case '/':
            return a/b;
        case '^':
            return pow(a,b);
        default :
            return 0;
        }
    }
    
    char OPSET[OPSETSIZE]= {
        '+','-','*','/','(',')','#','^'};
    
    Status In(char Test,char *TestOp)
    {
        
        int Find=false;
        for (int i=0; i< OPSETSIZE; i++)
        {
        
            if(Test == TestOp[i])
                Find= true;
        }
        return Find;
    }
    
    Status ReturnOpOrd(char op,char *TestOp)
    {
        
        for(int i=0; i< OPSETSIZE; i++)
        {
        
            if (op == TestOp[i])
                return i;
        }
    }
    
    char precede(char Aop, char Bop)
    {
        
        return Prior[ReturnOpOrd(Aop,OPSET)][ReturnOpOrd(Bop,OPSET)];
    }
    
    float EvaluateExpression(char* MyExpression)
    {
        
        // 算术表达式求值的算符优先算法
        // 设OPTR和OPND分别为运算符栈和运算数栈，OP为运算符集合
        SC *OPTR=NULL;       // 运算符栈，字符元素
        SF *OPND=NULL;       // 运算数栈，实数元素
        char TempData[20];
        float Data,a,b;
        char theta,*c,Dr[]= {
        '#','\0'};
        OPTR=Push(OPTR,'#');
        c=strcat(MyExpression,Dr);
        strcpy(TempData,"\0");//字符串拷贝函数
        while (*c!= '#' || OPTR->c!='#')
        {
        
            if (!In(*c, OPSET))
            {
        
                Dr[0]=*c;
                strcat(TempData,Dr);           //字符串连接函数
                c++;
                if (In(*c, OPSET))
                {
        
                    Data=atof(TempData);       //字符串转换函数(double)
                    OPND=Push(OPND, Data);
                    strcpy(TempData,"\0");
                }
            }
            else    // 不是运算符则进栈
            {
        
                switch (precede(OPTR->c, *c))
                {
        
                case '<': // 栈顶元素优先级低
                    OPTR=Push(OPTR, *c);
                    c++;
                    break;
                case '=': // 脱括号并接收下一字符
                    OPTR=Pop(OPTR);
                    c++;
                    break;
                case '>': // 退栈并将运算结果入栈
                    theta=OPTR->c;
                    OPTR=Pop(OPTR);
                    b=OPND->f;
                    OPND=Pop(OPND);
                    a=OPND->f;
                    OPND=Pop(OPND);
                    OPND=Push(OPND, Operate(a, theta, b));
                    break;
                } //switch
            }
        } //while
        return OPND->f;
    } //EvaluateExpression
    
    int main(void)
    {
        
        char s[128];
        cout<<"请输入表达式: "<<endl;
        cin>>s;
        cout<<"该表达式的值为: "<<endl;
        printf("%s\b=%g\n",s,EvaluateExpression(s));
        system("pause");
        return 0;
    }

## 【实验结果】 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dYX3RpbWk_size_16_color_FFFFFF_t_70 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dYX3RpbWk_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200207112824151.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dYX3RpbWk=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dYX3RpbWk_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200207113030205.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dYX3RpbWk=,size_16,color_FFFFFF,t_70