#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=)