简单表达式计算实用类
支持的运算如表所示
运算符号 | 释义 | 例子 |
---|---|---|
+ | 加法 | 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;
}
运行测试: