search

sinomoe / sino.moe

just a simple issue blog
http://sino.moe
0 stars 1 forks source link

基于链栈的计算器实现 #4

Open sinomoe opened 6 years ago

sinomoe commented 6 years ago

目录

概述

基于链栈实现计算器的思路主要有两种：

  1. 基于双栈的实现

    使用两个不同的栈分别储存运算符和运算数，当输入运算符时，比较栈内的运算符与待入栈的运算符的优先级来决定是否计算。最后通过循环计算全式，直到运算符栈为空为止。本实现难点主要在计算过程的控制。

  2. 基于中序转后序算法的单栈实现

    使用中序转后续算法，首先将中序式转换为后续式，然后通过堆栈进行计算。难点主要在中序转换到后续的过程，实现可以参考链接一、链接二。

上述两种算法都能达到目的，第一种算法直接明了，便于学习，但是运算符优先级比较的过程实现并不优雅，并且与计算的过程杂糅在一起，耦合比较严重。第二种算法层次清晰，将优先级比较和计算完全解耦，只需要在中序转后序的时候比较优先级即可，在后序式的计算中无需考虑优先级，因此第二种算法的通用性更好。

综合考虑到实现难度和学习理解的因素，最后选择了方法一来实现本计算器，如果在写完了之后还想要提高的话可以考虑使用方法二再实现一次。

链栈实现

顾名思义是使用链表结构储存的栈，在本实现中链栈的定义如下

template<class T>
class LinkedStack {
    struct Node {
        T value;
        Node *next;
    };
public:
    LinkedStack();

    ~LinkedStack();

    void push(T value);

    T pop();

    T getTop();

    int getLen();

    bool isEmpty();

private:
    Node *top;
    int len;
};

在定义上，使用了一个模板类储存链栈结构，这样就能很方便的定义不同类型的链栈。我们为链栈定义了一个私有结构体 Node，用来储存链栈的每个节点；定义了两个私有成员 top 和 len，分别储存链栈的栈顶和长度；除了构造和析构函数外定义了六个公有成员，pop 和 push 对应了入/出栈的操作，getTop 返回了栈顶，getLen 返回了栈长，isEmpty 判断栈是否为空。

计算器实现

如前文所述，本计算器由双栈实现，并利用状态机来进行循环计算，如下是计算器类的定义。

class Calculator {
    enum {
        WAITING = 0,
        CALCULATABLE
    };
public:
    Calculator();

    ~Calculator();

    // init 初始化状态及运算符和运算数
    void init();

    // getResult 输入等号
    double getResult();

    // inputOperator 输入运算符
    void inputOperator(char op);

    // inputOperand 输入运算数
    void inputOperand(double op);

private:
    // operators 运算符栈
    LinkedStack<char> *operators;

    // operands 运算数栈
    LinkedStack<double> *operands;

    // status 计算状态，WAITING 时不能计算，CALCULATABLE 时可计算
    int status;

    // pendingOperator 待入栈的运算符
    char pendingOperator;

    // checkCalculatable 检查是否可计算，可计算则返回真
    bool checkCalculatable();

    // checkOperator 检查待入栈运算符的优先级，并修改计算器状态
    void checkOperator(char op);

    // pushOperator 压入运算符栈
    void pushOperator(char op);

    // pushOperand 压入运算数栈
    void pushOperand(double op);

    // calculate 进行阶段性计算
    void calculate();
};

在定义上，在类内部使用枚举类型定义了计算器的两种状态（简化），只有当计算器处于 CALCULATABLE 状态时才能够进行局部计算；计算器类内部保存着两个栈，分别是运算符栈和运算数栈；除了构造和析构函数外，该类只对外暴露了三个方法，分别对应了输入运算符、运算数和获取结果的功能；其它各成员的意义如注释所示，如下便不多赘述。

从代码分析一次计算过程

下面通过一次计算过程来分析本实现的运行过程。在主函数中我们尝试运行如下代码，其等同计算过程 1+2x3/4=

int main() {
    Calculator cal;
    cal.inputOperand(1);
    cal.inputOperator('+');
    cal.inputOperand(2);
    cal.inputOperator('x');
    cal.inputOperand(3);
    cal.inputOperator('/');
    cal.inputOperand(4);
    cout << cal.getResult() << endl;
    return 0;
}

首先实例了一个 Calculator 对象 cal，在构造函数中

Calculator::Calculator() {
    this->operators = new(LinkedStack<char>);
    this->operands = new(LinkedStack<double>);
    this->status = WAITING;
}

我们创建了运算符栈 operators 和运算数栈 operands 并初始化了计算器的状态为 WAITING 此时计算器处于等待状态。紧接着执行到 cal.inputOperand(1); 为运算数栈 operands 压入了一个元素，此时相当于已经输入了操作数 1；接着执行到 cal.inputOperator('+'); 输入了第一个运算符，代码如下所示

void Calculator::inputOperator(char op) {
    this->pendingOperator = op;
    while (1) {
        this->checkOperator(op);
        if (this->status != CALCULATABLE)
            return;
        this->calculate();
    }
}

输入了运算符后不会立马将运算符压入运算符栈 operators，相反会将输入的运算符赋给 Calculator 对象的私有成员 pendingOperator ；然后在一个循环内通过 checkOperator(op) 来检查待入栈的运算数和运算符栈顶元素的优先级来更改本对象的状态 status，如果 status 不是可计算状态 CALCULATABLE 就返回，反之进行计算，直到不能计算为止。这里先不对 checkOperator 方法多做解释，后面会对其进行分析。

再次回到上面提到的，我们已经输入了运算数 1，现在紧接着输入了运算符 +，显然是不能计算的，所以这里在 checkOperator 中将 pendingOperator 压入了运算符栈，并修改状态为 WAITING，由于状态不是 CALCULATABLE 故在循环中就直接返回了。

接着执行 cal.inputOperand(2); 和前面输入运算数 1 的时候类似，我们将 2 压入了运算数栈；紧接着执行 cal.inputOperator('x');，我们将会输入第二个运算符 x，和上面输入运算符 + 时类似，现在的 pendingOperator 变成了 x，下面我们看看循环中的 checkOperator 是怎么工作的，下面是它的代码

// 检查符号栈的排列并更新计算状态
void Calculator::checkOperator(char op) {
    char top = this->operators->getTop();
    // 如果符号栈为空则直接入栈
    if (this->operators->getLen() == 0)
    {
        this->pushOperator(op);
        this->status = WAITING;
        this->pendingOperator = '\0';
    }// 如果符号栈不为空且输入的是 +/- 则表明可以计算前一个符号
    else if (op == '+' || op == '-')
    {
        this->status = CALCULATABLE;
    }// 如果符号栈不为空且输入的为 x// 且前一个输入的符号为 +/- 则不能计算，继续等待
    else if (top == '-' || top == '+')
    {
        this->pushOperator(op);
        this->status = WAITING;
        this->pendingOperator = '\0';
    }// 如果符号栈不为空且输入的为 x// 且前一个输入的符号为 x// 则可以计算钱一个符号
    else
    {
        this->status = CALCULATABLE;
    }
}

从代码得知，当符号栈为空（即初始状态，输入第一个运算符）时，输入的运算符可以直接入栈，然后将状态更新为 WAITING 并清除 pendingOperator；当符号栈不为空且输入的是 +/- 时，则能够直接计算前一个符号，此时将状态更新为 CALCULATABLE 并由 inputOperator 中的循环调用 calculate 计算；当符号栈不为空且输入的是 x// 且前一个输入的符号为 +/- 则不能计算，输入的运算符可以直接入栈，更改状态为 WAITING 并清除 pendingOperator；当符号栈不为空且输入的是 x// 且符号栈栈顶的符号为 x// 则可以计算符号栈栈顶的符号，然后修改状态为 CALCULATABLE 并由 inputOperator 中的循环调用 calculate 计算。

回到 cal.inputOperator('x');，显然此时运算符栈不为空，且符号栈栈顶为 + 待入栈为 x，满足第三个条件判断，所以将运算符 x 入栈，并将状态更改为 WAITING 然后清除待入栈运算符 pendingOperator；然后返回到循环中，由于状态不为 CALCULATABLE 故返回到主函数。

回到主函数，接着执行了 cal.inputOperand(3); 输入了运算数 3；然后执行到了 cal.inputOperator('/');，再次进入到循环中，调用 checkOperator，这时符号栈栈顶为 x 且输入的为 / 故进入第四个判断分支并将状态更新为 CALCULATABLE，返回到循环中时，由于状态为 CALCULATABLE 所以继续往下执行并调用 this->calculate();。

calculate 函数很简单，只是将运算数 operands 栈 pop出两个元素，并将运算数 operators 栈 pop 出一个元素，然后对其进行运算，最后将运算结果重新 push 进入运算数 operands 栈。回到我们执行的代码，运算数栈 pop 出了 2 和 3，运算符栈 pop 出了 x ，故结果为 6，然后将 6 重新 push 入运算数栈。现在的运算数栈为 (top)6->1(root)->null，运算符栈为 (top)+(root)->null。

计算完成后再次回到 inputOperator 中的循环，然后再次调用 checkOperator，这时 pendingOperator 还是 /，且符号栈顶为 +，满足了条件分支三，将 / 入栈并修改状态为 WAITING 最后清除 pendingOperator；回到 inputOperator 中的循环后，由于不满足状态为 CALCULATABLE 的条件，再次回到主函数。

最后在主函数中调用了 cal.getResult()，它的代码如下

// 循环计算栈内数据，直到符号栈为空
double Calculator::getResult() {
    this->status = CALCULATABLE;
    while (1) {
        this->calculate();
        if (this->operators->getLen() == 0)
            return this->operands->getTop();
    }
}

当输入等号后，会将计算器的状态设为 CALCULATABLE 然后循环调用 calculate 直到符号栈为为空，即计算完毕。回到我们的例子，最终符号栈为空，此时运算数栈只有一个元素 2.5，然后返回了这个元素。

至此一次完整的计算就完成了，1+2x3/4=2.5 也符合预期。

图形化

下面是效果图（GIF）

aaa

本来最开始是计划使用 qt5 来做图形界面的，但是由于对 qt 并不是很熟悉，考虑到实现效率问题，我将原来的 c++ 程序用 nodejs 移植了一遍，最后使用了我较为熟悉的 electron 来快速开发图形界面。

图形界面的实现并不是很复杂，但是在实现的过程中也学习到了一些以前没有深入理解的东西，比如数据视图绑定，使用 Object.defineProperty 来定义对象成员的 [[get]] 和 [[set]] 属性便能达到目的；还对 js 中的构造函数中的特权方法有了新的认识。

优点及不足

虽然只是一个很简单的程序，但是在设计上也有一些比较好的地方：

  1. 底层链栈的实现非常灵活，可复用性强。

  2. 使用了新的界面技术 electron，高效图形界面开发。

然而本计算器的实现只是一个基础的原型，还有很多缺陷和不足：

  1. 只考虑了四种基本算数运算，不支持更复杂的表达式。

由于设计的时候并没有想加入很多功能，所以只实现了四种基本运算，而且运算符比较少的情况下更容易进行优先级判断，如果加入更多的运算符，优先级比较判断部分的代码将会更加繁杂。

  1. 代码耦合

出于直观易懂的考虑，在实现上并没有使用中序转后续的算法，这样导致了代码的抽象程度不够，优先级的逻辑判断过程和算术计算过程耦合在一起，一旦加入新的运算符就会要加入很多逻辑判断语句，使得代码面条化。