Win32 字符串表达式计算

简单表达式计算实用类

支持的运算如表所示

表达式示例:

CCalculateUtils.h

#pragma once
#include <wtypesbase.h>
#include <tchar.h>
#include <vector>
#include <string>

#ifdef _UNICODE
using _tstring = std::wstring;
#else
using _tstring = std::string;
#endif

class BTreeNode
{
public:
    BTreeNode()
        :
        m_leftChild(nullptr),
        m_rightChild(nullptr)
    {

    }

    ~BTreeNode()
    {
        Delete(m_leftChild);
        Delete(m_rightChild);
    }

    void Delete(BTreeNode* pNode)
    {
        if (nullptr != pNode)
        {
            Delete(pNode->m_leftChild);
            pNode->m_leftChild = nullptr;
            Delete(pNode->m_rightChild);
            pNode->m_rightChild = nullptr;
            delete pNode;
        }
    }

public:
    BTreeNode* m_leftChild;
    BTreeNode* m_rightChild;
    _tstring m_strValue;
};

class CCalculateUtils
{
public:

    //
    // @brief: 计算字符串算术表达式的结果
    // @param: strExp               表达式, 如: "(2+3)*8-67/2*(4-3)+5"
    // @param: lfResult             计算结果
    // @ret: bool                   操作成功与否
    static bool CCalculate(const _tstring& strExp, double& lfResult);

private:

    //
    // @brief: 获取分解后的表达式元素
    // @param: lpExpBegin           表达式起始位置
    // @param: lpExpEnd             表达式结束位置
    // @param: outExp               分解后的表达式元素序列
    // @ret: bool                   操作成功与否
    static bool GetExpressionElements(LPCTSTR lpExpBegin, LPCTSTR lpExpEnd, std::vector<_tstring>& outExp);

    //
    // @brief: 构建表达式二叉树
    // @param: outExp               表达式元素序列
    // @ret: BTreeNode*             表达式二叉树根结点
    static BTreeNode* BuildBinaryTree(std::vector<_tstring>& outExp);

    //
    // @brief: 构建表达式二叉树
    // @param: pNode                表达式二叉树根结点
    // @ret: double                 计算结果
    static double CalcBinaryTree(const BTreeNode* pNode);

    //
    // @brief: 检查字符串是否为数字
    // @param: strItem              字符串
    // @ret: bool                   是否为数字
    static bool IsNumber(const _tstring& strItem);

    //
    // @brief: 检查字符串是否为运算符
    // @param: strItem              字符串
    // @ret: bool                   是否为运算符
    static bool IsOperator(const _tstring& strItem);

    //
    // @brief: 检查字符是否为运算符
    // @param: ch                   字符
    // @ret: bool                   是否为运算符
    static bool IsOperator(TCHAR ch);

    //
    // @brief: 比较运算符优先级
    // @param: strLeft              运算符1
    // @param: strRight             运算符2
    // @ret: int                    0: 优先级相等, >0: strLeft 优先级高于 strRight, <0: strLeft 优先级低于 strRight
    static int CompareOperator(const _tstring& strLeft, const _tstring& strRight);
};

CCalculateUtils.cpp

#include "CCalculateUtils.h"
#include <stack>
#include <map>
#include <queue>
#include <math.h>

//运算符优先级
std::map<_tstring, int> g_operatorLevel =
{
    {_T("^"), 2},
    {_T("*"), 1},
    {_T("/"), 1},
    {_T("+"), 0},
    {_T("-"), 0}
};

int CCalculateUtils::CompareOperator(const _tstring& strLeft, const _tstring& strRight)
{
    return g_operatorLevel.find(strLeft)->second - g_operatorLevel.find(strRight)->second;
}

bool CCalculateUtils::IsNumber(const _tstring& strItem)
{
    LPCTSTR lpBegin = strItem.c_str();
    LPCTSTR lpEnd = strItem.c_str();

    if (_istdigit(*lpBegin))
    {
        return true;
    }
    
    (void)_tcstod(lpBegin, (LPTSTR*)&lpEnd);
    if (lpBegin != lpEnd)
    {
        return true;
    }

    return false;
}

bool CCalculateUtils::IsOperator(TCHAR ch)
{
    if (_T('+') == ch ||
        _T('-') == ch ||
        _T('*') == ch ||
        _T('/') == ch ||
        _T('^') == ch
        )
    {
        return true;
    }

    return false;
}

bool CCalculateUtils::IsOperator(const _tstring& strItem)
{
    if (_T("+") == strItem ||
        _T("-") == strItem ||
        _T("*") == strItem ||
        _T("/") == strItem ||
        _T("^") == strItem
        )
    {
        return true;
    }

    return false;
}

BTreeNode* CCalculateUtils::BuildBinaryTree(std::vector<_tstring>& outExp)
{
    std::stack<_tstring> opStack;
    std::queue<_tstring> reversePolish;
    bool bSuccess = true;

    for (const auto& item : outExp)
    {
        if (IsNumber(item))
        {
            reversePolish.push(item);
        }
        else if (
            _T("+") == item ||
            _T("-") == item ||
            _T("*") == item ||
            _T("/") == item ||
            _T("^") == item ||
            _T("(") == item ||
            _T(")") == item
            )
        {
            _tstring strOperate = item;

            if (_T("(") == item)
            {
                opStack.push(item);
            }
            else if (_T(")") == item)
            {
                while (!opStack.empty())
                {
                    _tstring strOperateTop = opStack.top();
                    opStack.pop();
                    if (_T("(") == strOperateTop)
                    {
                        break;
                    }
                    else
                    {
                        reversePolish.push(strOperateTop);
                    }
                }
            }
            else
            {
                while (!opStack.empty())
                {
                    _tstring strTopOperate = opStack.top();
                    if (_T("(") == strTopOperate)
                    {
                        opStack.push(strOperate);
                        break;
                    }
                    else if (CompareOperator(strTopOperate, strOperate) >= 0)
                    {
                        reversePolish.push(strTopOperate);
                        opStack.pop();
                    }
                    else if (CompareOperator(strTopOperate, strOperate) < 0)
                    {
                        opStack.push(strOperate);
                        break;
                    }
                }

                if (opStack.empty())
                {
                    opStack.push(strOperate);
                }
            }
        }
        else
        {
            return false;
        }
    }

    //剩下的操作符入队
    while (!opStack.empty())
    {
        _tstring strTopOperate = opStack.top();
        reversePolish.push(strTopOperate);
        opStack.pop();
    }

    //将后缀表达式转化成二叉树
    std::stack<BTreeNode*> nodeStack;
    while (!reversePolish.empty())
    {
        _tstring strTopOperate = reversePolish.front();
        BTreeNode* pNode = new (std::nothrow) BTreeNode();
        if (nullptr == pNode)
        {
            bSuccess = false;
            break;
        }

        pNode->m_strValue = strTopOperate;

        if (IsNumber(strTopOperate))
        {
            nodeStack.push(pNode);
        }
        else
        {
            if (nodeStack.size() < 2)
            {
                bSuccess = false;
                break;
            }

            pNode->m_rightChild = nodeStack.top();
            nodeStack.pop();
            pNode->m_leftChild = nodeStack.top();
            nodeStack.pop();
            nodeStack.push(pNode);
        }
        reversePolish.pop();
    }

    if (nodeStack.empty())
    {
        return nullptr;
    }

    if (!bSuccess)
    {
        BTreeNode* pNode = nodeStack.top();
        delete pNode;
        pNode = nullptr;
        return nullptr;
    }

    return nodeStack.top();
}

bool CCalculateUtils::GetExpressionElements(LPCTSTR lpExpBegin, LPCTSTR lpExpEnd, std::vector<_tstring>& outExp)
{
    LPCTSTR lpBegin = lpExpBegin;

    //拆分算式元素
    std::vector<_tstring> vectorExpression;
    while (lpBegin < lpExpEnd)
    {
        //是运算符
        if (IsOperator(*lpBegin))
        {
            bool bLastOperator = false;
            bool bLastNumber = false;
            bool bNumber = IsNumber(lpBegin);
            if (!vectorExpression.empty() && IsOperator(vectorExpression.back()))
            {
                bLastOperator = true;
            }

            if (!vectorExpression.empty() && IsNumber(vectorExpression.back()))
            {
                bLastNumber = true;
            }

            //当前元素可以转为数字
            if (bNumber)
            {
                //最近元素是运算符或者表达式容器为空, 则当作操作数处理
                if (bLastOperator || vectorExpression.empty())
                {
                    LPCTSTR lpTemp = lpBegin;
                    (void)_tcstod(lpBegin, (LPTSTR*)&lpTemp);
                    _tstring strExp = lpBegin;
                    strExp.resize(lpTemp - lpBegin);
                    vectorExpression.push_back(strExp);
                    lpBegin = lpTemp;
                }
                //否则仅当作运算符处理
                else
                {
                    _tstring strExp = lpBegin;
                    strExp.resize(1);
                    vectorExpression.push_back(strExp);
                    lpBegin++;
                }
            }
            //当前元素是运算符
            else
            {
                //最近元素是数字或者表达式元素不为空, 则当作运算符处理
                if (bLastNumber || !vectorExpression.empty())
                {
                    _tstring strExp = lpBegin;
                    strExp.resize(1);
                    vectorExpression.push_back(strExp);
                    lpBegin++;
                }
                //其他情况认为不合法
                else
                {
                    return false;
                }
            }
        }
        //遇到操作数
        else if (IsNumber(lpBegin))
        {
            //遇到右括号与数字挨着, 则添加乘法运算符
            if (!vectorExpression.empty() && _T(")") == vectorExpression.back())
            {
                vectorExpression.push_back(_T("*"));
            }

            LPCTSTR lpTemp = lpBegin;
            (void)_tcstod(lpBegin, (LPTSTR*)&lpTemp);
            _tstring strExp = lpBegin;
            strExp.resize(lpTemp - lpBegin);
            vectorExpression.push_back(strExp);
            lpBegin = lpTemp;
        }
        //遇到括号优先级
        else if (_T('(') == *lpBegin)
        {
            LPCTSTR lpTemp = lpBegin + 1;
            int nDeep = 1;

            while (lpTemp < lpExpEnd)
            {
                if (_T('(') == *lpTemp) nDeep++;
                if (_T(')') == *lpTemp) nDeep--;
                if (0 == nDeep) break;
                lpTemp++;
            }

            //不允许括号不匹配
            if (0 != nDeep)
            {
                return false;
            }

            //不允许空括号()
            if (1 == (lpTemp - lpBegin))
            {
                return false;
            }

            //获取子表达式元素
            std::vector<_tstring> subExp;
            if (!GetExpressionElements(lpBegin + 1, lpTemp, subExp))
            {
                return false;
            }

            //遇到数字与左括号挨着, 则添加乘法运算符
            if (!vectorExpression.empty() && IsNumber(vectorExpression.back()))
            {
                vectorExpression.push_back(_T("*"));
            }

            vectorExpression.push_back(_T("("));
            for (const auto& item : subExp)
            {
                vectorExpression.push_back(item);
            }
            vectorExpression.push_back(_T(")"));

            lpBegin = lpTemp + 1;
        }
        else
        {
            return false;
        }
    }

    if (!vectorExpression.empty())
    {
        //末尾元素是运算符, 但是没有操作数, 则补全一下
        _tstring strOperator = vectorExpression.back();
        if (_T("*") == strOperator || _T("/") == strOperator)
        {
            vectorExpression.push_back(_T("1"));
        }
        else if (_T("+") == strOperator || _T("-") == strOperator)
        {
            vectorExpression.push_back(_T("0"));
        }
        else if (_T("^") == strOperator)
        {
            vectorExpression.push_back(_T("2"));
        }
    }

    outExp = vectorExpression;
    return true;
}

bool CCalculateUtils::CCalculate(const _tstring& strExp, double& lfResult)
{
    //去除空格
    _tstring strDest = strExp;
    _tstring strFind = _T(" ");
    size_t nFind = 0;

    //查找去除空格
    while (_tstring::npos != (nFind = strDest.find(strFind)))
    {
        strDest.replace(nFind, strFind.size(), _T(""));
    };

    if (strDest.empty())
    {
        return false;
    }

    //获取表达式元素
    LPCTSTR lpBegin = strDest.c_str();
    LPCTSTR lpEnd = lpBegin + strDest.size();
    std::vector<_tstring> outExp;
    if (!GetExpressionElements(strDest.c_str(), lpEnd, outExp))
    {
        return false;
    }

    //构建计算二叉树
    BTreeNode* pCalcTree = BuildBinaryTree(outExp);
    if (pCalcTree)
    {
        //计算结果
        lfResult = CalcBinaryTree(pCalcTree);
        delete pCalcTree;
        pCalcTree = nullptr;
    }

    return true;
}

double CCalculateUtils::CalcBinaryTree(const BTreeNode* pNode)
{
    double lfLeftt = 0.0f;
    double lfRight = 0.0f;

    //左右子结点为空, 则返回数字
    if (nullptr == pNode->m_leftChild && nullptr == pNode->m_rightChild)
    {
        return _tcstod(pNode->m_strValue.c_str(), nullptr);
    }

    //计算左结点结果
    if (nullptr != pNode->m_leftChild)
    {
        lfLeftt = CalcBinaryTree(pNode->m_leftChild);
    }

    //计算右结点结果
    if (nullptr != pNode->m_rightChild)
    {
        lfRight = CalcBinaryTree(pNode->m_rightChild);
    }

    if (_T("+") == pNode->m_strValue)
    {
        lfLeftt = lfLeftt + lfRight;
    }

    if (_T("-") == pNode->m_strValue)
    {
        lfLeftt = lfLeftt - lfRight;
    }

    if (_T("*") == pNode->m_strValue)
    {
        lfLeftt = lfLeftt * lfRight;
    }

    if (_T("/") == pNode->m_strValue)
    {
        lfLeftt = lfLeftt / lfRight;
    }

    if (_T("^") == pNode->m_strValue)
    {
        lfLeftt = pow(lfLeftt, lfRight);
    }

    return lfLeftt;
}

main.cpp

#include <iostream>
#include <vector>
#include <map>
#include <stdarg.h>
#include <tchar.h>
#include <windows.h>
#include <thread>
#include <strsafe.h>
#include "Win32Utils/CFileSplitUtils.h"
#include "Win32Utils/CPathUtils.h"
#include "Win32Utils/CTimeUtils.h"
#include "Win32Utils/CWaitableTimer.h"
#include "Win32Utils/CStrUtils.h"
#include "Win32Utils/CCalculateUtils.h"

int _tmain(int argc, LPCTSTR argv[])
{
    setlocale(LC_ALL, "");


    uint64_t ullBegin = CTimeUtils::GetCurrentTickCount();

    double lfValue1 = 0.0f;
    double lfValue2 = 0.0f;

    LPCTSTR ExpAry[] = {
        _T("2+(2-7)*2*(8-2)/2"),
        _T("1024^3"),
        _T("-512-512"),
        _T("2(3)5/2"),
        _T("2(3)5/2()"),
        _T("2(3)5/2("),
    };

    for (const auto& item : ExpAry)
    {
        _tprintf(_T("%s"), item);
        if (CCalculateUtils::CCalculate(item, lfValue1))
        {
            _tprintf(_T(" = %lf\n"), lfValue1);
        }
        else
        {
            _tprintf(_T(" = error!\n"));
        }
    }

    uint64_t ullEnd = CTimeUtils::GetCurrentTickCount();
    _tprintf(_T("cost time: %lldms\n"), ullEnd - ullBegin);

    return 0;
}

运行测试: