#include <stack>
#include <string>
#include <memory>
using namespace std;
/*本工具提供四则运算解析功能
使用时，引入本文件即可。
通过调用 Chion::Math::ParsStr("100+200*3/(54+89)");即可得到结果
注意：如果输入的字符串非法，则返回结果是一个空指针。
如果你对算法有兴趣，那么下面的说明可以了解一下：
我对输入的原始的字符串称为源字符串SourceString
对于从SourceString解析下来的一个元素称为SourceElement
SourceElement有可能是一个数字，一个运算符，一个左括号，一个右括号或者为空。
两个SourceElement如果都是运算符，可以进行优先级比较：
一种方法是调用SourceElement1.Compare(SourceElement2)
另一种方法是用减法运算 SourceElement1 -SourceElement2
根据结果来判断其大小：
1：SourceElement1大于SourceElement2
0：SourceElement1等于SourceElement2
-1：SourceElement1小于SourceElement2
-2：错误，说明两个中存在不是运算符的情况
通过SourceString::GetNextObject()可以不断解析到新的元素。直到SourceElement为空，表示结束。
算法如下(算法思路摘自百度百科)：
首先需要分配2个栈，一个作为临时存储运算符的栈S1，一个作为输入逆波兰式的栈S2（空栈），从中缀式的左端开始取字符，逐序进行如下步骤：
（1）若取出的字符是操作数，则分析出完整的运算数，该操作数直接送入S2栈
（2）若取出的字符是运算符，则将该运算符与S1栈栈顶元素比较，如果该运算符优先级(不包括括号运算符)大于S1栈栈顶运算符优先级，则将该运算符进S1栈，否则，将S1栈的栈顶运算符弹出，送入S2栈中，直至S1栈栈顶运算符低于（不包括等于）该运算符优先级，最后将该运算符送入S1栈。
（3）若取出的字符是“（”，则直接送入S1栈顶。
（4）若取出的字符是“）”，则将距离S1栈栈顶最近的“（”之间的运算符，逐个出栈，依次送入S2栈，此时抛弃“（”。
（5）重复上面的1~4步，直至处理完所有的输入字符
（6）当所有字符处理完之后，如果S1中还有数据，则逐个出栈，依次送入S2栈。
完成以上步骤，S2栈便为逆波兰式输出结果。不过S2应做一下逆序处理。便可以按照逆波兰式的计算方法计算了！
*/
namespace Chion{
/*枚举了元素对象可能存在的情况*/
typedef enum{
TYPE_EMPTY, //空
TYPE_NUMBER, //数字
TYPE_OPERATOR, //运算符
TYPE_BRACKETS_L, //左括号
TYPE_BRACKETS_R, //右括号
}ENUM_OBJECT_TYPE;
/*元素对象，它表示从源字符串上解析出来的一个单元*/
struct SourceElement
{
/*构造一个空的对象*/
SourceElement(){
m_type = TYPE_EMPTY;
m_value = 0.0;
m_op = '\0';
}
/*构造一个括号对象，如果参数有误，则构造一个空对象*/
SourceElement(ENUM_OBJECT_TYPE type){
m_value = 0.0;
m_op = '\0';
switch (type)
{
case TYPE_BRACKETS_L:
case TYPE_BRACKETS_R:
m_type = type;
break;
case TYPE_EMPTY:
case TYPE_NUMBER:
case TYPE_OPERATOR:
default:
m_type = TYPE_EMPTY;
break;
}
}
/*构造一个操作符对象，如果参数有误，则构造一个空对象。参数取值只能是'+'、'-'、'*'、'/'*/
SourceElement(char op){
if (op == '+'
||
op == '-'
||
op == '*'
||
op == '/'
)
{
m_type = TYPE_OPERATOR;
m_op = op;
}
else
{
m_type = TYPE_EMPTY;
m_op = '\0';
}
m_value = 0.0;
}
/*构造一个数字对象*/
SourceElement(double value)
{
m_type = TYPE_NUMBER;
m_value = value;
m_op = '\0';
}
ENUM_OBJECT_TYPE type() const{
return m_type;
}
/*当类型为数字时，返回数值。其它类型时，返回0，此时0无意义。*/
double value(){
if (m_type == TYPE_NUMBER)
{
return m_value;
}
else
{
return 0.0;
}
}
/*当类型为操作符时，返回操作符'+' '-' '*' '/'。其它类型时，返回'\0'*/
char op(){
if (m_type == TYPE_OPERATOR)
{
return m_op;
}
else
{
return '\0';
}
}
int Compare(const SourceElement& obj)
{
if (this->m_type != ENUM_OBJECT_TYPE::TYPE_OPERATOR
||
obj.type() != ENUM_OBJECT_TYPE::TYPE_OPERATOR)
{
return -2;
}
else
{
if (this->m_op == '*' || this->m_op == '/')
{
if (obj.m_op == '*' || obj.m_op == '/')
{
return 0;
}
else
{
return 1;
}
}
else
{
if (obj.m_op == '*' || obj.m_op == '/')
{
return -1;
}
else
{
return 0;
}
}
}
}
int operator-(const SourceElement &obj){
if (this->m_type != ENUM_OBJECT_TYPE::TYPE_OPERATOR
||
obj.type() != ENUM_OBJECT_TYPE::TYPE_OPERATOR)
{
return -2;
}
else
{
if (this->m_op == '*' || this->m_op == '/')
{
if (obj.m_op == '*' || obj.m_op == '/')
{
return 0;
}
else
{
return 1;
}
}
else
{
if (obj.m_op == '*' || obj.m_op == '/')
{
return -1;
}
else
{
return 1;
}
}
}
}
private:
ENUM_OBJECT_TYPE m_type;
double m_value;
char m_op;
};
/*源字符串的封装对象，封装对源字符串的一些操作*/
struct SourceString{
SourceString(const string &str)
:m_pos(0){
//只保留四则运算中的有用字符
for (auto &e : str)
{
if (
(e >= '0' && e <= '9')
||
e == '.'
||
e == '+' || e == '-' || e == '*' || e == '/'
||
e == '(' || e == ')'
)
{
m_str += e;
}
}
}
/*
从m_pos位置开始，在源字符串上解析出一个元素，解析完毕，m_pos指向元素下一个位置
如果解析失败，m_pos已经超出字符串范围，返回一个type为空的对象。
*/
SourceElement GetNextObject()
{
//解析到了尽头，无法再继续解析，返回空对象
if (m_pos >= m_str.size())
{
return SourceElement();
}
//获取一个字符
char c = m_str[m_pos];
switch (c)
{
//运算符号，合法（游标可进位）
case '+':
case '*':
case '/':
m_pos++;
return SourceElement(c);
/*
如果遇到减号，需要独立判断，看这是一个运算符，还是属于数字前面的负号
当它满足两个条件时，该减号为负号：
1.它的后面是数字
2.它的前面是加减乘除或者左括号或者前面没有其它字符
*/
case '-':
if (m_pos + 1 < m_str.size() && m_str[m_pos + 1] >= '0' && m_str[m_pos + 1] <= '9'
&&
(m_pos == 0||
m_str[m_pos - 1] == '('||
m_str[m_pos - 1] == '+'||
m_str[m_pos - 1] == '-'||
m_str[m_pos - 1] == '*'||
m_str[m_pos - 1] == '/'))
{
string number = ParseNumber();
return number.size() ? SourceElement(atof(number.c_str())) : SourceElement();
}
else
{
m_pos++;
return SourceElement(c);
}
//左括号，合法（游标可进位）
case '(':
m_pos++;
return SourceElement(TYPE_BRACKETS_L);
//右括号，合法（游标可进位）
case ')':
m_pos++;
return SourceElement(TYPE_BRACKETS_R);
case '.'://小数点出现在第一个字符是不正常的，非法（游标不进位）
return SourceElement();
default://数字，需要连续解析
{
string number = ParseNumber(); //要解析的数字
return number.size()? SourceElement(atof(number.c_str())):SourceElement();
}
}
}
private:
/*
它从m_pos位置开始，解析出一个数字来。解析完毕后，m_pos指向数字的下一个位置。
如果解析失败，它返回空字符串
*/
string ParseNumber(){
string number;
bool bDot(false); //小数点是否出现的标志
//往后继续解析
for (; m_pos < m_str.size();)
{
//获取一个字符
char n = m_str[m_pos];
if (n == '-' && number.size()==0)//如果是减号，且出现在开头位置，表示这是一个负号
{
number += n;
m_pos++;
}
else if (n >= '0' && n <= '9') //如果是数字，则追加到number，游标进位
{
number += n;
m_pos++;
}
else if (n == '.') //如果是小数点，首次出现是合法的，追加并游标进位。否则判为非法，游标不进位
{
if (bDot == false)
{
number += n;
m_pos++;
bDot = true;
}
else
{
return "";
}
}
else//如果是其它字符，表示在此终止，游标不进位，停留在该字符上
{
break;
}
}
return number;
}
private:
string m_str;
int m_pos;
};
class Math{
public:
static std::shared_ptr<double> ParseStr(const string &sourceStr){
SourceString source(sourceStr);
stack<SourceElement> s1; //运算符栈
stack<SourceElement> s2; //逆波兰式栈
//从左至右逐个对象地解析
for (SourceElement obj = source.GetNextObject();
obj.type() != ENUM_OBJECT_TYPE::TYPE_EMPTY;
obj = source.GetNextObject())
{
switch (obj.type())
{
case ENUM_OBJECT_TYPE::TYPE_NUMBER: //数字直接入栈
s2.push(obj);
break;
case ENUM_OBJECT_TYPE::TYPE_OPERATOR://运算符则要判断来处理
{
//如果栈顶元素是运算符，且优先级低于等于当前运算符，则弹出放入s2。
while(
s1.size()
&&
(
obj.Compare(s1.top()) == 0 //等于
||
obj.Compare(s1.top()) == -1 //低于
)
)
{
s2.push(s1.top());
s1.pop();
}
s1.push(obj);
}
break;
case ENUM_OBJECT_TYPE::TYPE_BRACKETS_L: //左括号直接入栈
s1.push(obj);
break;
case ENUM_OBJECT_TYPE::TYPE_BRACKETS_R: //右括号，清空S1栈顶，直到遇见左括号或清空全部
{
while (s1.size())
{
if (s1.top().type() == TYPE_OPERATOR){
s2.push(s1.top());
s1.pop();
}
else if (s1.top().type() == TYPE_BRACKETS_L)
{
s1.pop();
break;
}
else
{
break;
}
}
}
break;
default:
break;
}
}
//把S1剩下的都放入S2
while (s1.size())
{
s2.push(s1.top());
s1.pop();
}
//由于s2中的逆波兰式是倒过来的，我们先把它倒置到s1中
while (s2.size())
{
s1.push(s2.top());
s2.pop();
}
//开始计算结果
while (s1.size())
{
auto obj = s1.top();
s1.pop();
switch (obj.type())
{
case TYPE_NUMBER://如果是数字，则放入S2
s2.push(obj);
break;
case TYPE_OPERATOR://如果是运算符，则从s2中取两个数来计算
{
if (s2.size() < 2)
{
//出错了，s2中的数不足两个
return nullptr;
}
auto numb2 = s2.top(); //先出来的是第二个运算值
s2.pop();
auto numb1 = s2.top();
s2.pop();
//根据运算符，进行计算
switch (obj.op())
{
case '+':
s2.push(SourceElement(numb1.value() + numb2.value()));
break;
case '-':
s2.push(SourceElement(numb1.value() - numb2.value()));
break;
case '*':
s2.push(SourceElement(numb1.value() * numb2.value()));
break;
case '/':
if (abs(numb2.value()) < 0.00000001){
//出错了，被除数不能为零
return nullptr;
}
s2.push(SourceElement(numb1.value() / numb2.value()));
break;
default:
//出错了，这里不应该出现四则运算外的运算符
return nullptr;
break;
}
}
break;
default:
//出错了，这里不应该出现数字和运算符外其它的类型
return nullptr;
}
}
if (s2.size() != 1)
{
//出错了，合法的计算结果里，此时应该只有一个值
return nullptr;
}
return std::shared_ptr<double>(new double(s2.top().value()));
}
};
}
![C语言第四章自述2第四章 选择结构程序设计[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)