【数据结构】基于栈的中缀算式表达式求值

梦里梦外; 2023-02-18 03:19 9阅读 0赞

### 基于栈的中缀算式表达式求值 ###

*  问题：
 *  要求：
 *  运行软件
 *  调试
 *  引用函数
 *   *  将字符串转换成浮点数
     *   *  atof函数：
         *  strtod函数：
         *  memset函数
 *  判断符号优先级表
 *  代码实现：

# 问题： #

输入一个中缀算术表达式，求解表达式的值。运算符包括+、-、\*、/、(、)、=，参加运算的数为double类型且为正数。（要求：直接针对中缀算术表达式进行计算，不能转换为后缀或前缀表达式再进行计算，只考虑二元运算即可。）

# 要求： #

（1）创建名为kcsj12.cpp的文件，并编写程序实现指定功能；  
（2）输入：多组数据，每组数据一行，对应一个算术表达式，每个表达式均以“=”结尾。当表达式只有一个“=”时，输入结束。参加运算的数为double类型；  
（3）输出：对于每组数据输出一行，为表达式的运算结果。输出保留两位小数。  
输入样例和输出样例：

> 输入：  
> 2+2=  
> 20\*（4.5-3）=  
> =  
> 输出：  
> 4.00  
> 30.00

# 运行软件 #

CLion

# 调试 #

debug

# 引用函数 #

## 将字符串转换成浮点数 ##

### atof函数： ###

atof()是C 语言标准库中的一个字符串处理函数，功能是把字符串转换成浮点数，所使用的头文件为<stdlib.h>。

示例代码：

#include<stdlib.h>
    #include<stdio.h>
    int main()
    {
        
    double d;
    char str[] = "123.456";
    d=atof(str);
    printf("string=%sdouble=%lf\n",str,d);
    return 0;
    }

### strtod函数： ###

strtod是C语言及C++中的重要函数，功能是将字符串转换成浮点数，表头文件是\#include <stdlib.h>，相关函数有atoi，atol，strtod，strtol。

示例代码：

#include<stdlib.h>
    #include<stdio.h>
    void main()
    {
        
        char *endptr;
        char a[] = "12345.6789";
        char b[] = "1234.567qwer";
        char c[] = "-232.23e4";
        printf( "a=%lf\n", strtod(a,NULL) );
        printf( "b=%lf\n", strtod(b,&endptr) );
        printf( "endptr=%s\n", endptr );
        printf( "c=%lf\n", strtod(c,NULL) );
    }

### memset函数 ###

memset是计算机中C/C++语言初始化函数。作用是将某一块内存中的内容全部设置为指定的值， 这个函数通常为新申请的内存做初始化工作。

char chs[20];
    memset(chs,'#', sizeof(char)*20);

# 判断符号优先级表 #

(1)先乘除，后加减；  
(2)从左算到右；  
(3)先括号内，后括号外

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

*  由规则(1), 先进行乘除运算，后进行加减运算，所以有 “+” < “*"; “+” < “!”; "*” >。
 *  由规则(2), 运算遵循左结合性，当两个运算符相同时，先出现的运算符优先级高，所以有

> “+” > “+”;  
> “-” > “-”;  
> " \* " > " \* ";  
> “/” > “/”。

*  由规则(3), 括号内的优先级高，＋、－、＊和I为81 时的优先性均低千 (" “但高于 " )”。表中的 “(” = “)” 表示当左右括号相遇时，括号内的运算已经完成。为了便千实现，假设每个表达式均以"\#“开始，以”\#" 结束。所以"\#" = “\#” 表示整个表达式求值完毕。")“与 “(”、＂＃”与”)" 以及"(“与”\#" 之间无优先关系，这是因为表达式中不允许它们相继出现，一旦遇到这种情况，则可以认为出现了语法错误。在 下面的讨论中，我们暂假定所输人的表达  
    式不会出现语法错误。

# 代码实现： #

#include <iostream>
    #include <stdlib.h>
    #include <cstring>
    #define MAXSIZE 100//初始分配的存储空间
    #define OK 0
    #define  OVERFLOW 1
    #define ERROR 1
    typedef char SElemType;
    typedef int Status;
    using namespace std;
    
    //定义字符栈
    typedef struct {
        
        SElemType *base;//栈底指针，始终指向栈底元素，构造之前和销毁之后base的值为NULL
        SElemType *top;//栈顶指针，始终指向栈顶元素的下一个位置
        int stackSize;//当前分配的存储容量，以元素为单位
    } SqStackOPTR;
    
    //定义数字栈
    typedef struct {
        
        double *base;//栈底指针，始终指向栈底元素，构造之前和销毁之后base的值为NULL
        double *top;//栈顶指针，始终指向栈顶元素的下一个位置
        int stackSize;//当前分配的存储容量，以元素为单位
    } SqStackOPND;
    
    //字符栈的初始化
    Status InitStack(SqStackOPTR &S) {
        
        S.base = new SElemType[MAXSIZE]; //分配空间
        if (!S.base) exit(OVERFLOW);//分配失败，异常退出
        S.top = S.base;
        S.stackSize = MAXSIZE;
        return OK;
    }
    
    //数字栈的初始化
    Status InitStack(SqStackOPND &S) {
        
        S.base = new double[MAXSIZE]; //分配空间
        if (!S.base) exit(OVERFLOW);//分配失败，异常退出
        S.top = S.base;
        S.stackSize = MAXSIZE;
        return OK;
    }
    
    //字符栈入栈操作
    Status Push(SqStackOPTR &S, SElemType e) {
        
        if (S.top - S.base == MAXSIZE) //说明栈满
            return ERROR;
        *S.top++ = e;//元素e进栈
        return OK;
    }
    
    //数字栈入栈操作
    Status Push(SqStackOPND &S, double e) {
        
        if (S.top - S.base == MAXSIZE) //说明栈满
            return ERROR;
        *S.top++ = e;//元素e进栈
        return OK;
    }
    
    //字符栈出栈操作
    SElemType Pop(SqStackOPTR &S) {
        
        char e;
        if (S.top == S.base) return ERROR; //栈空
        e = *--S.top;//这里其实是将栈顶的指针向下移了以为，没有真正的删除元素   用e返回其值
        return e;
    }
    
    //数字栈出栈操作
    double Pop(SqStackOPND &S) {
        
        double e;
        if (S.top == S.base) return ERROR; //栈空
        e = *--S.top;//这里其实是将栈顶的指针向下移了以为，没有真正的删除元素   用e返回其值
        return e;
    }
    
    //取字符栈栈顶元素
    SElemType GetTop(SqStackOPTR S) {
        
        char e;
        if (S.top == S.base) return ERROR;//栈空
        e = *(S.top - 1);//返回
        return e;
    }
    
    //取数字栈栈顶元素
    double GetTop(SqStackOPND S) {
        
        double e;
        if (S.top == S.base) return ERROR;//栈空
        e = *(S.top - 1);//返回
        return e;
    }
    
    //判断字符的方法，判断输入的字符是数字还是运算符
    //如果是数字，那么返回0，如果是运算符，返回1
    Status In(SElemType e) {
        
        int isNumber;
        switch (e) {
        
            case '+':
            case '-':
            case '*':
            case '/':
            case '(':
            case ')':
            case '=':
                isNumber = 1;
                break;
            default:
                isNumber = 0;
                break;
        }
        return isNumber;
    
    }
    
    //定义一个判定运算符栈的栈顶元素与读入的运算符之间优先关系的函数
    char Precede(SElemType top, char ch) {
        
    /*
     * 算数四则运算遵循以下3条规则
     * （1）先乘除，后加减
     * （2）从左算到右
     * （3）先括号内，后括号外
     */
        char symbol;//定义一个字符串来接收> = <
    
    
    
        switch (top) {
        
            case '+':
            case '-':
                switch (ch) {
        
                    case '+':
                    case '-':
                    case ')':
                    case '=':
                        symbol = '>';
                        break;
                    case '*':
                    case '/':
                    case '(':
                        symbol = '<';
                        break;
                }
                break;
            case '*':
            case '/':
                switch (ch) {
        
                    case '+':
                    case '-':
                    case '*':
                    case '/':
                    case ')':
                    case '=':
                        symbol = '>';
                        break;
                    case '(':
                        symbol = '<';
                        break;
                }
                break;
            case '(':
                switch (ch) {
        
                    case '+':
                    case '-':
                    case '*':
                    case '/':
                    case '(':
                        symbol = '<';
                        break;
                    case ')':
                        symbol = '=';
                        break;
                }
                break;
            case ')':
                switch (ch) {
        
                    case '+':
                    case '-':
                    case '*':
                    case '/':
                    case ')':
                    case '=':
                        symbol = '>';
                        break;
                }
                break;
            case '=':
                switch (ch) {
        
                    case '+':
                    case '-':
                    case '*':
                    case '/':
                    case '(':
                        symbol = '<';
                        break;
                    case '=':
                        symbol = '=';
                        break;
                }
                break;
        }
        return symbol;
    }
    
    //定义一个二元运算的方法，来进行+ - * /
    double Operate(double a, SElemType top, double b) {
        
        double sum = 0;
        switch (top) {
        
            case '+':
                sum = a + b;
                break;
            case '-':
                sum = a - b;
                break;
            case '*':
                sum = a * b;
                break;
            case '/':
                if (b != 0) sum = a / b;//如果是0怎么办
                break;
        }
        return sum;
    }//20*（4.5-3）=
    
    double EvaluateExpression(char ch) {
        
        //定义两个栈，分别为OPTR栈（放运算符）OPND栈（放数字）
        SqStackOPTR OPTR;//定义字符栈
        SqStackOPND OPND;//定义数字栈
        InitStack(OPTR);//初始化OPTR栈
        InitStack(OPND);//初始化OPND栈
        Push(OPTR, '=');//将表达式起始符’#‘压入OPTR栈
        char chs[20];//定义一个字符数组，来实现数字转换为字符串
      memset(chs,'#', sizeof(char)*20);//将字符数组的元素设置为‘#’
    
        while (ch != '=' || GetTop(OPTR) != '=') {
        //表达式没有扫描完毕或OPTR的栈顶元素不为“=”
            if (!In(ch)) {
        
                //这里应该将字符串转换为数字
                for (int i = 0; i <strlen(chs) ; i++) {
        
                    if (chs[i]=='#' && !In(ch)){
        //如果数组的第i个元素不为‘#’或不为符号
                        chs[i]=ch;
                        cin>>ch;
                    } else{
        
                        break;
                    }
                }
                double d=atof(chs);//把字符串转换成浮点数 double
    //            double d1=strtod(chs,NULL);//将字符串转换成浮点数
                Push(OPND,d);
                memset(chs,'#', sizeof(char)*20);//将字符数组的元素设置为‘#’
            } else {
        
                switch (Precede(GetTop(OPTR), ch)) {
        
                    case '<':
                        Push(OPTR, ch);cin>>ch;
                        break;
                    case '>':
                        char theta;
                        double b;
                        double a;
                        theta = Pop(OPTR);
                        b = Pop(OPND);
                        a = Pop(OPND);
                        double sum;
                        sum = Operate(a, theta, b);
                        Push(OPND,  sum);
                        break;
                    case '=':
                        Pop(OPTR);
                        cin>>ch;
                        break;
                }
            }
        }
        return GetTop(OPND);
    }
    
    int main() {
        
    
        while (1) {
        
            char ch;
            cin >> ch;
            if (ch == '=')break;
            double res = EvaluateExpression(ch);
           printf("%.2lf",res);
        }
        return 0;
    }

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

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JsYWNrX0N1c3RvbWVy_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200615203028641.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JsYWNrX0N1c3RvbWVy,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JsYWNrX0N1c3RvbWVy_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200615204553407.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JsYWNrX0N1c3RvbWVy,size_16,color_FFFFFF,t_70