花心胡萝卜 C++ 递归向下法 计算器

实现计算器

当前模式的递归向下法

当前情况下, 对于同优先级运算符连续的算式, 如(1 - 3 + 7, 3 4 / 5 6)
会因为左递归而计算错误.

我们没有采用规避左递归的办法, 而是重新设计了两个同优先级节点来解决.

计算器完整代码

// Node.h   节点类定义
#ifndef _NODE_H_
#define _NODE_H_

#include <cfloat>
#include <vector>

namespace Hades
{
    // 接口类, 实现对象语义, 防止对象复制
    class NonCopyable
    {
    protected:
        NonCopyable() {}
    private:
        NonCopyable(const NonCopyable&) {}
        const NonCopyable& operator=(const NonCopyable&) = delete;
    };

    // 节点类 基类
    class Node : private NonCopyable    // 接口继承, 使用private
    {
    public:
        Node() {}
        virtual ~Node() {}

        virtual double Calc() const = 0;
    };

    // 数字类
    class NumberNode : public Node
    {
    private:
        double number_;

    public:
        NumberNode(const double number) : number_(number) {}

        double Calc() const override    // 重写的
        {
            return number_;
        }
    };

    // 一元运算符类
    class UnaryNode : public Node
    {
    protected:
        Node* node_;

    public:
        UnaryNode(Node* node = nullptr) : node_(node)
        {

        }
        ~UnaryNode()
        {
            if (node_)
                delete node_;
        }
    };

    // 相同优先级运算基类
    class MultipleNode : public Node
    {
    protected:
        std::vector<Node*> childs_;
        // 正true负false,  乘true除false
        std::vector<bool> flags_;
    public:
        MultipleNode(Node* child = nullptr, bool flags = true)
        {
            AppendChild(child, flags);
        }
        void AppendChild(Node* child, bool flags = true)
        {
            childs_.push_back(child);
            flags_.push_back(flags);
        }
        ~MultipleNode()
        {
            for (auto child : childs_)
            {
                delete child;
            }
        }
    };

    // 求和类
    class SumNode : public MultipleNode
    {
    public:
        explicit SumNode(Node* child = nullptr) : MultipleNode(child) {}
        double Calc() const override
        {
            auto positive = flags_.begin();
            double dRet = 0.0;
            for (auto child : childs_)
            {
                if (*positive)
                {
                    dRet += child->Calc();
                }
                else
                {
                    dRet -= child->Calc();
                }
                ++positive;
            }
            return dRet;
        }
    };

    // 乘积类
    class ProductNode : public MultipleNode
    {
    public:
        explicit ProductNode(Node* child = nullptr) : MultipleNode(child) {}
        double Calc() const override
        {
            auto product = flags_.begin();
            double dRet = 1.0;
            for (auto child : childs_)
            {
                if (*product)
                    dRet *= child->Calc();
                else
                {
                    double dCalcRet = child->Calc();
                    if (dCalcRet > -DBL_EPSILON && dCalcRet < DBL_EPSILON)
                        dRet = 0.0;
                    else
                        dRet /= child->Calc();
                }
                ++product;
            }
            return dRet;
        }
    };

    // 负数类
    class MinusNode : public UnaryNode
    {
    public:
        MinusNode(Node* node = nullptr) : UnaryNode(node)
        {

        }

        double Calc() const
        {
            return (0 - node_->Calc());
        }
    };

    // =========================================================================== 
    // 已经通过程序设计避免了左递归, 以下类废弃
    // 如果使用消除左递归的办法, 以下类还可使用
    // ===========================================================================

    class BinaryNode : public Node
    {
    protected:
        Node* left_;
        Node* right_;

    public:
        BinaryNode(Node* left = nullptr, Node* right = nullptr) : left_(left), right_(right)
        {

        }
        ~BinaryNode()
        {
            if (left_)
                delete left_;
            if (right_)
                delete right_;
        }
    };

    class AddNode : public BinaryNode
    {
    public:
        AddNode(Node* left = nullptr, Node* right = nullptr) : BinaryNode(left, right) {}

        double Calc() const override
        {
            return left_->Calc() + right_->Calc();
        }
    };

    class SubNode : public BinaryNode
    {
    public:
        SubNode(Node* left = nullptr, Node* right = nullptr) : BinaryNode(left, right) {}

        double Calc() const override
        {
            return left_->Calc() - right_->Calc();
        }
    };

    class MulitplyNode : public BinaryNode
    {
    public:
        MulitplyNode(Node* left = nullptr, Node* right = nullptr) : BinaryNode(left, right) {}

        double Calc() const override
        {
            return left_->Calc() * right_->Calc();
        }
    };

    class DivisionNode : public BinaryNode
    {
    public:
        DivisionNode(Node* left = nullptr, Node* right = nullptr) : BinaryNode(left, right) {}

        double Calc() const override
        {
            double divisor = right_->Calc();
            if (divisor < DBL_EPSILON && divisor > -DBL_EPSILON)    // 判断0
            {
                return divisor;
            }
            return left_->Calc() / right_->Calc();
        }
    };
}

#endif // _NODE_H_

// Parser.h 分析类定义
#ifndef _PARSER_EX_H_
#define _PRSER_EX_H_

namespace Hades 
{
    class Scanner;
    class Node;

    class Parser
    {
    public:
        Parser(Scanner& scanner);
        ~Parser();

        void Parse();
        double Calculate() const;

    private:
        Scanner& scanner_;
        Node* tree_;

        Node* Expr();
        Node* Term();
        Node* Factor();
    };
}
#endif // _PARSER_EX_H_

// Parser.cpp   分析类代码
#include "Parser.h"

#include "Scanner.h"
#include "Node.h"

#include <iostream>
using std::cout;
using std::endl;

namespace Hades
{

    Parser::Parser(Scanner& scanner) : scanner_(scanner)
    {
    }


    Parser::~Parser()
    {
    }

    void Parser::Parse()
    {
        tree_ = Expr();
    }

    double Parser::Calculate() const
    {
        return tree_->Calc();
    }

    Node * Parser::Expr()
    {
        Node* node = Term();
        EToken token = scanner_.Token();
        // 未消除左递归的代码, 连续相同优先级的算式, 如 1-3+7 这样的会计算错误
        //if (token == TOKEN_PLUS)
        //{
        //    scanner_.Accept();
        //    Node* rightNode = Expr();
        //    node = new AddNode(node, rightNode);
        //}
        //else if (TOKEN_MINUS == token)
        //{
        //    scanner_.Accept();
        //    Node* rightNode = Expr();
        //    node = new SubNode(node, rightNode);
        //}

        // 处理相同优先级
        if (TOKEN_PLUS == token || TOKEN_MINUS == token)
        {
            MultipleNode* multipleNode = new SumNode(node);
            do 
            {
                scanner_.Accept();
                Node* nextNode = Term();
                multipleNode->AppendChild(nextNode, TOKEN_PLUS == token);
                // 改变操作符
                token = scanner_.Token();
            } while (TOKEN_PLUS == token || TOKEN_MINUS == token);
            node = multipleNode;
        }

        return node;
    }

    Node * Parser::Term()
    {
        Node* node = Factor();
        EToken token = scanner_.Token();

        // 未消除左递归的代码, 连续优先级算式, 如 3*4/5*6 会计算错误
        //if (token == TOKEN_MULTIPLY)
        //{
        //    scanner_.Accept();
        //    Node* rightNode = Term();
        //    node = new MulitplyNode(node, rightNode);
        //}
        //else if (TOKEN_DIVISION == token)
        //{
        //    scanner_.Accept();
        //    Node* rightNode = Term();
        //    node = new DivisionNode(node, rightNode);
        //}

        // 处理相同优先级
        if (TOKEN_MULTIPLY == token || TOKEN_DIVISION == token)
        {
            MultipleNode* multipleNode = new ProductNode(node);
            do
            {
                scanner_.Accept();
                Node* nextNode = Factor();
                multipleNode->AppendChild(nextNode, TOKEN_MULTIPLY == token);
                // 改变操作符
                token = scanner_.Token();
            } while (TOKEN_MULTIPLY == token || TOKEN_DIVISION == token);
            node = multipleNode;
        }
        return node;
    }

    Node * Parser::Factor()
    {
        Node* node = nullptr;
        EToken token = scanner_.Token();

        if (TOKEN_LPARENTHESES == token)
        {
            scanner_.Accept();
            node = Expr();
            if (TOKEN_RPARENTHESES == scanner_.Token())
            {
                scanner_.Accept();
            }
            else
            {
                // 错了
                cout << "缺失右括号!" << endl;
                // 抛出异常
            }
        }
        else if (TOKEN_NUMBER == token)
        {
            node = new NumberNode(scanner_.Number());
            scanner_.Accept();
        }
        else if (TOKEN_MINUS == token)    // 负号
        {
            scanner_.Accept();
            node = new MinusNode(Factor());
        }
        else
        {
            // 错了
            cout << "输入表达式有误!" << endl;
            // 抛出异常
        }
        return node;
    }

}

// Scanner.h    扫描类定义
#ifndef _SCANNER_H_
#define _SCANNER_H_

#include <string>


namespace Hades
{
    enum EToken
    {
        TOKEN_END,
        TOKEN_ERROR,
        TOKEN_NUMBER,
        TOKEN_PLUS,
        TOKEN_MINUS,
        TOKEN_MULTIPLY,
        TOKEN_DIVISION,
        TOKEN_LPARENTHESES,
        TOKEN_RPARENTHESES
    };
    
    using std::string;

    class Scanner
    {
    private:
        const string buf_;
        std::size_t curPos_;
        EToken token_;
        double number_;

        void SkipWhite();

    public:
        Scanner(const string buf);
        ~Scanner();

        double Number() const;
        EToken Token() const;

        EToken Accept();    // 开始解析
    };
}
#endif // _SCANNER_H_

// Scanner.h    扫描类代码
#include <cstdlib>
#include "Scanner.h"

namespace Hades
{
    void Scanner::SkipWhite()
    {
        while (isspace(buf_[curPos_]))
            ++curPos_;
    }

    Scanner::Scanner(const string buf)
        : buf_(buf), curPos_(0), number_(0.0),
        token_(TOKEN_ERROR)
    {
        // 预处理
        Accept();
    }

    Scanner::~Scanner()
    {
    }

    double Scanner::Number() const
    {
        return number_;
    }

    EToken Scanner::Token() const
    {
        return token_;
    }
    
    EToken Scanner::Accept()
    {
        token_ = TOKEN_ERROR;
        number_ = 0.0;
        do
        {
            if (curPos_ >= buf_.length())
                break;
            SkipWhite();
            switch (buf_[curPos_])
            {
            case '+':
                ++curPos_;
                token_ = TOKEN_PLUS;
                break;
            case '-':
                ++curPos_;
                token_ = TOKEN_MINUS;
                break;
            case '*':
                ++curPos_;
                token_ = TOKEN_MULTIPLY;
                break;
            case '/':
                ++curPos_;
                token_ = TOKEN_DIVISION;
                break;

            case '0':
            case '1':
            case '2':
            case '3':
            case '4':
            case '5':
            case '6':
            case '7':
            case '8':
            case '9':
            case '.':
            {
                token_ = TOKEN_NUMBER;
                char* pTmp = nullptr;
                number_ = strtod(&buf_[curPos_], &pTmp);
                curPos_ = pTmp - &buf_[0];
            }
            break;
            case '(':
                ++curPos_;
                token_ = TOKEN_LPARENTHESES;
                break;
            case ')':
                ++curPos_;
                token_ = TOKEN_RPARENTHESES;
                break;
            case '\0':
            case '\r':
            case '\n':
            case EOF:
                token_ = TOKEN_END;
                break;
            default:
                ++curPos_;
                break;
            }
        } while (false);

        return token_;
    }
}

// main.cpp 主程序
#include <iostream>

#include "Node.h"
#include "Scanner.h"
#include "Parser.h"

int main()
{
    using namespace std;
    using namespace Hades;

    do 
    {
        cout << "# ";
        string szBuf;
        getline(cin, szBuf);
        Scanner scanner(szBuf);
        Parser parser(scanner);
        parser.Parse();
        cout << "> " << parser.Calculate() << endl;
    } while (true);

    return 0;
}

工程说明

• VS2013以上版本(因为用了auto关键字)
• 工程目录视图:
  
• 因为没有学到异常, 所以没有写异常处理代码
• 输入错误的表达式会崩溃

工程下载

• 使用VS2017RC编写, VS2013以上版本可直接打开

  • 需要更换开发工具集
• 点我下载CalcDemo

如有错误,请提出指正!谢谢.

本文由 花心胡萝卜 创作，采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: 2017-02-20 at 03:50 pm