Win32 字符串表达式计算

简单表达式计算实用类

支持的运算如表所示

运算符号释义例子
+加法1024+512
-减法1024-512
*乘法1024*1024
/除法1024/128
^平方1024^2
%取模(求余数)10%3
(优先级左括号(1024+512)*8
)优先级右括号(1024+512)*8

表达式示例:

表达式有效性备注
2+(2-7)*2*(8-2)/2有效
1024^3有效1024的3次方
2(5+15)有效等同于2*(5+15)
2(5+15)+有效等同于2(5+15)+0
2(5+15)*有效等同于2(5+15)*1
+10--10有效等同于10-(-10)
-10++10有效等同于(-10)+10
2*()无效不允许括号内为空
2*(3+5无效缺失右括号
2++无效缺失操作数
2--无效缺失操作数

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 <ctgmath>

//运算符优先级
std::map<_tstring, int> g_operatorLevel =
{
    {_T("^"), 2},
    {_T("*"), 1},
    {_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 ||
        _T('^') == ch
        )
    {
        return true;
    }

    return false;
}

bool CCalculateUtils::IsOperator(const _tstring& strItem)
{
    if (_T("+") == strItem ||
        _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 ||
            _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)
    {
        if (lfLeftt * lfRight < 0)
        {
            double value = ::floor(lfLeftt / lfRight);
            lfLeftt = lfLeftt - (value * lfRight);
        }
        else
        {
            lfLeftt = ::fmod(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;
}

运行测试:

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/331319.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

头像空白问题

当用户没有设置头像时&#xff0c;我们可以使用用户名第一个字来当头像 主要涉及一个截取&#xff0c;截取字符串第一个字 变量名.charAt(0) 如果变量名为null或者undefine 那么就会报错 使用可选链操作符 &#xff1f; 当前面的值为nul或undefine时&#xff0c;就不会执行…

CSS||选择器

目录 作用 分类 基础选择器 标签选择器 ​编辑类选择器 id选择器 通配符选择器 作用 选择器&#xff08;选择符&#xff09;就是根据不同需求把不同的标签选出来这就是选择器的作用。 简单来说&#xff0c;就是选择标签用的。 选择器的使用一共分为两步&#xff1a; 1.…

代码随想录算法训练营第23天 | 669. 修剪二叉搜索树 + 108.将有序数组转换为二叉搜索树 + 538.把二叉搜索树转换为累加树

今日任务 669. 修剪二叉搜索树 108.将有序数组转换为二叉搜索树 538.把二叉搜索树转换为累加树 总结篇 669. 修剪二叉搜索树 - Medium 题目链接&#xff1a;力扣&#xff08;LeetCode&#xff09;官网 - 全球极客挚爱的技术成长平台 给你二叉搜索树的根节点 root &#xf…

代码随想录算法训练营29期|day 22 任务以及具体安排

235. 二叉搜索树的最近公共祖先 class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if(root null) return null;//向左遍历if(root.val > p.val && root.val > q.val){TreeNode left lowestCommonAncestor(roo…

MySQL表的基本插入查询操作详解

博学而笃志&#xff0c;切问而近思 文章目录 插入插入更新 替换查询全列查询指定列查询查询字段为表达式查询结果指定别名查询结果去重 WHERE 条件基本比较逻辑运算符使用LIKE进行模糊匹配使用IN进行多个值匹配 排序筛选分页结果更新数据删除数据截断表聚合函数COUNTSUMAVGMAXM…

C语言——atoi函数解析

目录 前言 atoi函数的介绍 atoi函数的使用 atoi函数的模拟实现 前言 对于atoi函数大家可能会有些陌生&#xff0c;不过当你选择并阅读到这里时&#xff0c;请往下阅读&#xff0c;我相信你能对atoi函数熟悉该函数的头文件为<stdlib.h> 或 <cstdlib> atoi函数的…

被遗忘在角落的RPA,成了提升AI Agent执行能力的天选神器

LLM&#xff08;Large Language Models&#xff09;刚爆发之时&#xff0c;很多人认为RPA要完了&#xff0c;自然语言交互API操作足以干掉任何UI自动化工具。 然而&#xff0c;大语言模型应用发展到AI Agent这一步&#xff0c;大家才发现API并不是万能的。Agent平台雨后春笋一…

【开源项目】经典开源项目实景三维数字孪生泰山

飞渡科技数字孪生文旅运营中心&#xff0c;基于文旅单位的运营管理、服务质量以及游客需求&#xff0c;通过数字孪生、AR/VR、大数据分析等技术&#xff0c;为景区打造虚实融合、超沉浸体验的专属虚拟数字场景&#xff0c;实现文旅领域的数据可视化、产业数字化以及智能化管理。…

Django Web开发(day4)——数据模型使用与填充网站数据(对数据库的基本操作)

本博客将会涉及: Django 数据模型的使用视频数据的导入admin 后台的使用 1、Django 数据模型的使用 在上一篇中完成了网站的数据模型的创建,在数据模型创建之后,Django 会为我们的数据模型创建一套数据库抽象的 API 接口,以供我们进行检索数据、创建数据、更新和修改数据…

vim 编辑器如何同时注释多行以及将多行进行空格

当然可以&#xff0c;以下是我对您的文字进行润色后的版本&#xff1a; 一、场景 YAML文件对空格的要求非常严格&#xff0c;因此在修改YAML时&#xff0c;我们可能需要批量添加空格。 二、操作步骤 请注意&#xff1a;您的所有操作都将以第一行为基准。也就是说&#xff0…

滚动菜单ListView

activity_main.xml <include layout"layout/title"/> 引用上章自定义标题栏 <?xml version"1.0" encoding"utf-8"?> <LinearLayout xmlns:android"http://schemas.android.com/apk/res/android"xmlns:app&qu…

BigeMap在Unity3d中的应用,助力数字孪生

1. 首先需要用到3个软件&#xff0c;unity&#xff0c;gis office 和 bigemap离线服务器 Unity下载地址:点击前往下载页面(Unity需要 Unity 2021.3.2f1之后的版本) Gis office下载地址:点击前往下载页面 Bigemap离线服务器 下载地址: 点击前往下载页面 Unity用于数字孪生项…

计算机系统基础知识揭秘:硬件、处理器和校验码

计算机系统基础知识揭秘&#xff1a;硬件、处理器和校验码 一、计算机系统基础知识的重要性二、计算机系统硬件2.1、内存和存储设备2.2、输入输出设备 三、中央处理器&#xff08;CPU&#xff09;3.1、运算器3.2、控制器3.3、寄存器组3.4、多核CPU 四、数据表示4.1、原码、反码…

前端项目配置 Dockerfile 打包后镜像部署无法访问

Dockerfile 配置如下&#xff1a; FROM node:lts-alpineWORKDIR /app COPY . . RUN npm install RUN npm run buildEXPOSE 3001CMD ["npm", "run", "preview"]构建镜像 docker build -t vite-clarity-project .启动镜像容器 docker run -p 30…

《C++入门篇》——弥补C不足

文章目录 前言一.命名空间二.缺省参数三.函数重载四.引用4.1引用做参数4.2引用做返回值 五.内联函数六.小语法6.1auto6.2范围for6.3空指针 前言 C是业内一门久负盛名的计算机语言&#xff0c;从C语言发展起来的它&#xff0c;不仅支持C语言的语法&#xff0c;还新添加了面向对…

MySQL之视图索引

学生表&#xff1a;Student (Sno, Sname, Ssex , Sage, Sdept) 学号&#xff0c;姓名&#xff0c;性别&#xff0c;年龄&#xff0c;所在系 Sno为主键 课程表&#xff1a;Course (Cno, Cname,) 课程号&#xff0c;课程名 Cno为主键 学生选课表&#xff1a;SC (Sno, Cno, Score)…

华为设备NAT的配置

实现内网外网地址转换 静态转换 AR1&#xff1a; sys int g0/0/0 ip add 192.168.10.254 24 int g0/0/1 ip add 22.33.44.55 24 //静态转换 nat static global 22.33.44.56 inside 192.168.10.1 动态转换 最多有两台主机同时访问外网 AR1&#xff1a; sys int g0/0/0 ip add…

C语言之【函数】篇章以及例题分析

文章目录 前言一、函数是什么&#xff1f;二、C语言中函数的分类1、库函数2、自定义函数 三、函数的参数1、实际参数&#xff08;实参&#xff09;2、形式参数&#xff08;形参&#xff09; 四、函数的调用1、传值调用2、传址调用3、专项练习3.1 素数判断3.2 闰年判断3.3 二分查…

【OpenCV学习笔记17】- 平滑图像

这是对于 OpenCV 官方文档中 图像处理 的学习笔记。学习笔记中会记录官方给出的例子&#xff0c;也会给出自己根据官方的例子完成的更改代码&#xff0c;同样彩蛋的实现也会结合多个知识点一起实现一些小功能&#xff0c;来帮助我们对学会的知识点进行结合应用。 如果有喜欢我笔…

【数据结构】栈的远房亲戚——队列

队列的基本概念 前言一、队列的定义二、队列的重要术语三、队列的基本操作四、数据结构的三要素4.1 线性表的三要素4.2 栈的三要素4.3 队列的三要素 结语 前言 大家好&#xff0c;很高兴又和大家见面啦&#xff01;&#xff01;&#xff01; 在经过前面内容的介绍&#xff0c;…