前言

写在前面的话：数据结构与算法。

对于初识数据结构的小伙伴们，鉴于后面的数据结构的构建会使用到同tag前面的内容，包括具体数据结构的应用，所使用到的数据结构，也是自己构建的，未使用系统的库文件，因此，建议这类小伙伴们按顺序进行学习；

对于想查询有关资料的小伙伴们，可以选择性地浏览。希望大家都能有所收获～

栈的应用（三）

本章为栈的第三个应用：

问题描述：如何计算一个字符串表达式的值？

咱也可以从另一个角度来认识这个问题： —如何制作一个简易的计算器？，实际上，要想实现一个计算器的功能，是一个非常复杂的问题，

下面我们将问题简化一下，假设此表达式中，运算符只有：“+”，“-”，“*”，“/”，阶乘，方幂，这六种再加上括号，于是，我们有以下的栈结构实现（EvaluAlgor.h）：

本质来说，该算法并不算完善，读者可以思考一下，该算法中存在什么问题？

/*
 * 作者：易果啥笔
 * 时间：2021.8.20
 * 内容：栈的典型应用三：求一个字符串表达式的数值
 *
 */

#ifndef STACK_EVALUALGOR_H
#define STACK_EVALUALGOR_H
#define N_OPTR 9 //运算符总数
#include "Stack.h"
#include <cmath>
#include "ParenMatch.h"

typedef enum {ADD,SUB,MUL,DIV,POW,FAC,L_P,R_P,EOE} Operator;

//将运算符与上述枚举对应
Operator optrRank(char optr){
    switch (optr) {
        case '+' : return ADD;
        case '-' : return SUB;
        case '*' : return MUL;
        case '/' : return DIV;
        case '^' : return POW;
        case '!' : return FAC;
        case '(' : return L_P;
        case ')' : return R_P;
        case '\0' : return EOE;
        default: exit(-1);

    }
}


//pri[]数组用于描述不同运算符之间的优先级关系
const char pri[N_OPTR][N_OPTR] = {
        '>','>','<','<','<','<','<','>','>',
        '>','>','<','<','<','<','<','>','>',
        '>','>','>','>','<','<','<','>','>',
        '>','>','>','>','<','<','<','>','>',
        '>','>','>','>','>','<','<','>','>',
        '>','>','>','>','>','>',' ','>','>',
        '<','<','<','<','<','<','<','=',' ',
        ' ',' ',' ',' ',' ',' ',' ',' ',' ',
        '<','<','<','<','<','<','<',' ','=',
};

//readNumber()用于获取从某数字字符开始的完整一个数

void readNumber(char*& S,Stack<float>& p){
    p.push((float)(*S-'0'));
    while(isdigit(*(++S)))
        p.push(p.pop()*10+(*S-'0')); //整数部分，注意到 '123' - '0' = 123
    if('.' != *S) return;
    float xiaoshu = 1;
    while(isdigit(*(++S)))
        p.push(p.pop()+(*S-'0')*(xiaoshu/=10)); //小数部分
}

//orderBetween()用于判定操作符之间的优先级关系
char orderBetween(char optr1,char optr2){
    return pri[optrRank(optr1)][optrRank(optr2)]; //直接比较
}


//calcu()函数用于求一个(阶乘)或两个数的运算

//先求阶乘
int factorial(int n){
    if(n<0)
        exit(-1);
    else if(n == 1) return 1;
    else return n*factorial(n-1); //递归实现
}

int calcu(char optr,int pOpnd){return factorial(pOpnd); }

//重载calcu()方法使之适用于两个数之间的运算


float calcu(float pOpnd1,char optr,float pOpnd2) {
    if (optr == '/' && pOpnd2 == 0) exit(-1); //除数不能为零
    switch (optr) {
        case '+' :
            return pOpnd1 + pOpnd2;
            break;
        case '-' :
            return pOpnd1 - pOpnd2;
            break;
        case '*' :
            return pOpnd1 * pOpnd2;
            break;
        case '/' :
            return pOpnd1 / pOpnd2;
            break;
        case '^' :
            return pow(pOpnd1, pOpnd2); //借用cmath库中的求幂函数pow()
        default:
            exit(-1);
    }
}


//evaluate()为求值核心算法
    float evaluate(char *S) {
        if( ! paren(S,0,length(S)) ) exit(-1); //不匹配时
        else{
            Stack<float> opnd;
            Stack<char> optr; //运算符栈，操作符栈
            optr.push('\0');
            while (!optr.Empty()) {
                if (isdigit(*S)) {
                    readNumber(S, opnd);
                } else
                    switch (orderBetween(optr.top(), *S)) {
                        case '<':
                            optr.push(*S);
                            S++;
                            break;
                        case '=':
                            optr.pop();
                            S++;
                            break;
                        case '>':
                            char op = optr.pop();
                            if ('!' == op) {
                                float pOpnd = opnd.pop();
                                if ((int) pOpnd == pOpnd) {
                                    opnd.push(calcu(op, (int) pOpnd));
                                } else exit(-1); //小数没有阶乘

                            } else {
                                float pOpnd2 = opnd.pop(), pOpnd1 = opnd.pop();
                                opnd.push(calcu(pOpnd1, op, pOpnd2));
                            }
                            break;
                    }
            }
            return opnd.pop();
        }
    }

#endif //STACK_EVALUALGOR_H

在evaluate()数值求解算法中，先使用了Paren()方法验证括号是否匹配（参考栈的应用二）。请读者细细体会栈在这种算法中所起的作用。

在main.cpp文件中我们可以验证它的正确性：

/*
 * 作者：易果啥笔
 * 时间：2021.8.20
 * 内容：栈的应用
 *
 */

#include <iostream>
#include "Stack.h"
#include "ParenMatch.h"
#include "EvaluAlgor.h"

using namespace std;

//遍历函数print
template <typename T> void print(T& e){ cout<<e; };

int main() {
    
    //应用三：求一个字符串表达式的值
    char expression2[40] = "10^3+23/2-(56*7)+5!";
    cout<<"10^3+23/2-(56*7)+5!表达式的值为："<<evaluate(expression2)<<"  "<<(10*10*10+23/2.0-(56*7)+5*4*3*2*1)<<endl;

    return 0;
}

仔细思考，你可以发现，这个算法是不支持负数参与计算的，这也是我前文所说的问题所在。读者可以思考一下，如何修改代码，使之支持负数参与运算。