2023年11月29日发(作者：)
【C++】算数表达式求值（易扩充版）
⽹上有很多的算数表达式求值的代码，但是不易扩充，⽽且对各种形式的表达式适配很差，特别是对“负号”和“减号”的区别⼏乎没有，
这⾥贴上我⾃⼰写的⼀个算数表达式的代码。⾄于求解原理请参照⽹络上的其他博客
//map
⾸先我们把运算符都在⼀个⾥注册⼀下，数值为该运算符的优先级
// $#%e_ “”“”“”“”“‘
这⾥添加的、、、、这些运算符分别指代对数运算、⾃然对数运算、根式运算、科学记数法标记符、特殊的负号标记符（实际使⽤时可以仍写
-’”
）
std::map<char, int> mps;
void init()
{
mps['+'] = 4; mps['-'] = 4;
mps['*'] = 3; mps['/'] = 3;
mps['_'] = 2;
mps['$'] = 1; mps['#'] = 1;
mps['^'] = 0; mps['%'] = 0; mps['e'] = 0;
mps['('] = 16; mps[')'] = 16;
}
注意到这⾥我们把括号运算符的优先级设定为16，原因可以⾃⼰尝试理解
//
括号匹配，当然觉得不需要可以不写，这⾥我们可以做⼀个宏定义
#define CHECK_brackets
bool judge(std::string& value)
{
stack<char> s;
for (int i = 0; i < value.size(); i++)
{
if (value[i] == '(' || value[i] == '[' || value[i] == '{') s.push(value[i]);
else if (value[i] == ')') { if (s.top() != '(') return false; s.pop(); }
else if (value[i] == ']') { if (s.top() != '[') return false; s.pop(); }
else if (value[i] == '}') { if (s.top() != '{') return false; s.pop(); }
}
if (!s.empty()) return false;//
这⾏代码其实可以不要，因为在计算器中，默认会为⾏尾添加上括号。
return true;
}
然后是⼀个对中缀表达式处理的函数
//TAB“-”“””“
负责删除输⼊内的空格、等字符，并判断是负号还是减号，并对错误的符号进⾏了错误抛出。
std::string delete_space(std::string& value)
{
inti();
#ifdef CHECK_brackets
if (!judge(value)) throw std::runtime_error("brackets error");
#endif
std::string ans, error = "unknown character: ";
int leftbrackets = 0;
for (int i = 0; i < value.size(); i++)
{
if (value[i] == ' ' || value[i] == 'b' || value[i] == 'n') continue;
if (value[i] == '(') leftbrackets++;
else if (value[i] == ')') leftbrackets--;
else if (value[i] == '[') { leftbrackets++; value[i] = '('; }
else if (value[i] == ']') { leftbrackets++; value[i] = ')'; }
else if (value[i] == '{') { leftbrackets++; value[i] = '('; }
else if (value[i] == '}') { leftbrackets++; value[i] = ')'; }
else if (value[i] == '-' && (i == 0 || ((ans.back() < '0' || ans.back() > '9') && ans.back() != '.' && ans.back() != ')')))
value[i] = '_';//
这⾥把负号与减号区别开来
else if ((value[i] < '0' || value[i] > '9') && !mps.count(value[i]) && value[i] != '.') { error.push_back(value[i]); throw std::runtime_error(error); }
ans.push_back(value[i]);
}
while (leftbrackets--) ans.push_back(')');
return ans;
}
然后是中缀转后缀表达式
//
将中缀表达式转化为后缀表达式
std::string postfix_expression(std::string& value)
{
std::string ans;
stack<char> s;
bool flag = true;
for (int i = 0; i < value.size(); i++)
{
if ((value[i] <= '9' && value[i] >= '0') || value[i] == '.') ans.push_back(value[i]);
else
{
ans.push_back(' ');
switch (value[i])
{
case '(':
s.push(value[i]);
flag = true;
break;
case ')':
while (!s.empty() && s.top() != '(') { ans.push_back(s.top()); s.pop(); }
s.pop();
break;
default:
int t = mps[value[i]];
while (!s.empty() && mps[s.top()] <= t) { ans.push_back(s.top()); s.pop(); }
s.push(value[i]);
break;
}
}
}
while (!s.empty()) { ans.push_back(s.top()); s.pop(); }
return ans;
}
然后我预留了两个函数，以⽅便读取数据
//
单⽬运算符从这⾥取数据
void getone(stack<double>& s, double& k)
{
if (!s.empty()) { k = s.top(); s.pop(); }
else throw std::runtime_error("expression error");
return;
}
//
双⽬运算符从这⾥取数据
void gettwo(stack<double>& s, double& a, double& b) { getone(s, b); getone(s, a); }
最后就是计算，当然，我把上述的所有函数直接在这个函数内调⽤了，所以最后只需要调⽤这个函数就⾏了
//
最终计算的函数，直接调⽤这个函数来完成计算
double calculate(std::string& value)
{
value = delete_space(value);
value = postfix_expression(value);
stack<double> s;
double cur = 0;
bool flag = false;
double dot = 1;
for (int i = 0; i < value.size(); i++)
{
if (value[i] == ' ' && flag){ s.push(cur); cur = 0; flag = false; dot = 1; }
else if (value[i] <= '9' && value[i] >= '0')
{
if (dot != 1) { cur += dot * (value[i] - '0'); dot *= 0.1; flag = true; }
else { cur *= 10; cur += value[i] - '0'; flag = true; }
}
else if (value[i] == '.')
{
if (dot == 1) { dot = 0.1; flag = true; }
else throw std::runtime_error("expression error");
}
else
{
if (flag) { s.push(cur); cur = 0; flag = false; dot = 1; }
double a, b;
switch (value[i])
{
case '+':
gettwo(s, a, b); s.push(a + b);
break;
case '-':
gettwo(s, a, b); s.push(a - b);
break;
case '*':
gettwo(s, a, b); s.push(a * b);
break;
case '/':
gettwo(s, a, b); s.push(a / b);
break;
case '^':
gettwo(s, a, b); s.push(pow(a, b));
break;
case '%':
gettwo(s, a, b); s.push(pow(b, 1 / a));
break;
case '$':
gettwo(s, a, b); s.push(log(b) / log(a));
break;
case 'e':
gettwo(s, a, b); s.push(a * pow(10, b));
break;
break;
case '_':
getone(s, a); s.push(-a);
break;
case '#':
getone(s, a); s.push(log(a));
break;
default:
break;
}
}
}
if (s.empty()) s.push(cur);
return s.top();
}
只需要输⼊string类型的算数表达式，此函数会⾃动求解并返回，如果遇到错误，也会抛出错误说明，可以使⽤try来测试。最后补上此代码
的符号优先级
1、括号"("、")"
2、次⽅运算"^"、根式运算"%"(⽰例：3%8=2，“%”前为开根号的次数，后为被开根号的数)、科学记数法"e"
3、对数运算"$"(⽰例：2$8=3，“$”前为底数，后为真数，注意不可以使⽤ e 来表⽰⾃然对数的底数，请使⽤“#”代替“$“来做对 e 的对数，例如：#2)
4、负号"-"
5、乘法"*"、除法"/"
6、加法"+"、减法"-"
如果要添加⼀个符号，可以在上⾯的 init 函数中对符号进⾏注册，并在最后的求解函数中，switch 中添加运算⽅式即可。（添加⽅式请参
照其他的运算符）
发布评论