在 C++ 中解析数学表达式
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/11703082/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
parsing math expression in c++
提问by Emiliano Gustavo Nunez
I have a question about Parsing Trees:
我有一个关于解析树的问题：
I have a string (math expresion estring), for example: (a+b)*c-(d-e)*f/g. I have to parse that expression in a Tree:
我有一个字符串（数学表达式 estring），例如：(a+b)*c-(d-e)*f/g. 我必须在树中解析该表达式：
class Exp{};
class Term: public Exp{
int n_;
}
class Node: Public Exp{
Exp* loperator_;
Exp* roperator_;
char operation; // +, -, *, /
}
What algorithm can I use to build a tree which represents the expresion string above?
我可以使用什么算法来构建代表上述表达式字符串的树？
回答by Kos
Use the Shunting-yard algorithm. The wikipedia description is quite comprehensive, I hope it will suffice.
使用调车码算法。维基百科的描述相当全面，我希望它就足够了。
You can also try to write a formal grammar, for example a parsing-expression grammar, and use a tool to generate a parser. This site about PEGslists 3 C/C++ libraries for PEG parsing.
您也可以尝试编写形式化语法，例如解析表达式语法，并使用工具生成解析器。这个关于 PEG 的站点列出了 3 个用于 PEG 解析的 C/C++ 库。
回答by Anirudh Ramanathan
(a+b)*c-(d-e)*f/gis an in-fix expression.
(a+b)*c-(d-e)*f/g是一个固定表达式。
To easily make a tree, convert that into a Prefix expression first.
要轻松制作tree，请先将其转换为 Prefix 表达式。
From the Example,
prefix of (A * B) + (C / D)is + (* A B) (/ C D)
从示例中，前缀(A * B) + (C / D)为+ (* A B) (/ C D)
(+)
/ \
/ \
(*) (/)
/ \ / \
A B C D
((A*B)+(C/D))
Your tree then looks has + as its root node. You can continue populating the left and right sub-tree, about each operator.
然后你的树看起来有 + 作为它的根节点。您可以继续填充关于每个运算符的左右子树。
Also, this linkexplains Recursive Descent Parsing in detail, and can be implemented.
另外，这个链接详细解释了递归下降解析，可以实现。
回答by jahhaj
First step is to write a grammar for your expressions. Second step for such a simple case is to write a recursive descent parser, that's the algorithm I would recommend. Here's the wiki page on recursive descent parsers which has a good looking C implementation.
第一步是为您的表达式编写语法。对于这种简单情况，第二步是编写递归下降解析器，这是我推荐的算法。这是递归下降解析器的 wiki 页面，它有一个漂亮的 C 实现。
回答by BLUEPIXY
#include <algorithm>
#include <iostream>
#include <string>
#include <cctype>
#include <iterator>
using namespace std;
class Exp{
public:
// Exp(){}
virtual void print(){}
virtual void release(){}
};
class Term: public Exp {
string val;
public:
Term(string v):val(v){}
void print(){
cout << ' ' << val << ' ';
}
void release(){}
};
class Node: public Exp{
Exp *l_exp;
Exp *r_exp;
char op; // +, -, *, /
public:
Node(char op, Exp* left, Exp* right):op(op),l_exp(left), r_exp(right){}
~Node(){
}
void print(){
cout << '(' << op << ' ';
l_exp->print();
r_exp->print();
cout << ')';
}
void release(){
l_exp->release();
r_exp->release();
delete l_exp;
delete r_exp;
}
};
Exp* strToExp(string &str){
int level = 0;//inside parentheses check
//case + or -
//most right '+' or '-' (but not inside '()') search and split
for(int i=str.size()-1;i>=0;--i){
char c = str[i];
if(c == ')'){
++level;
continue;
}
if(c == '('){
--level;
continue;
}
if(level>0) continue;
if((c == '+' || c == '-') && i!=0 ){//if i==0 then s[0] is sign
string left(str.substr(0,i));
string right(str.substr(i+1));
return new Node(c, strToExp(left), strToExp(right));
}
}
//case * or /
//most right '*' or '/' (but not inside '()') search and split
for(int i=str.size()-1;i>=0;--i){
char c = str[i];
if(c == ')'){
++level;
continue;
}
if(c == '('){
--level;
continue;
}
if(level>0) continue;
if(c == '*' || c == '/'){
string left(str.substr(0,i));
string right(str.substr(i+1));
return new Node(c, strToExp(left), strToExp(right));
}
}
if(str[0]=='('){
//case ()
//pull out inside and to strToExp
for(int i=0;i<str.size();++i){
if(str[i]=='('){
++level;
continue;
}
if(str[i]==')'){
--level;
if(level==0){
string exp(str.substr(1, i-1));
return strToExp(exp);
}
continue;
}
}
} else
//case value
return new Term(str);
cerr << "Error:never execute point" << endl;
return NULL;//never
}
int main(){
string exp(" ( a + b ) * c - ( d - e ) * f / g");
//remove space character
exp.erase(remove_if(exp.begin(), exp.end(), ::isspace), exp.end());
Exp *tree = strToExp(exp);
tree->print();
tree->release();
delete tree;
}
//output:(- (* (+ a b ) c )(/ (* (- d e ) f ) g ))
回答by jxh
You can use this grammar to create your expression.
您可以使用此语法来创建表达式。
exp:
/* empty */
| non_empty_exp { print_exp(); }
;
non_empty_exp:
mult_div_exp
| add_sub_exp
;
mult_div_exp:
primary_exp
| mult_div_exp '*' primary_exp { push_node('*'); }
| mult_div_exp '/' primary_exp { push_node('/'); }
;
add_sub_exp:
non_empty_exp '+' mult_div_exp { push_node('+'); }
| non_empty_exp '-' mult_div_exp { push_node('-'); }
;
primary_exp:
| '(' non_empty_exp ')'
| NUMBER { push_term(); }
;
And the following for your lexer.
以下是您的词法分析器。
[ \t]+ {}
[0-9]+ { yylval.number = atoi(yytext); return NUMBER; }
[()] { return *yytext; }
[*/+-] { return *yytext; }
The expression is built as you go, using these routines:
使用以下例程随时构建表达式：
std::list<Exp *> exps;
/* push a term onto expression stack */
void push_term (int n) {
Term *t = new Term;
t->n_ = n;
exps.push_front(t);
}
/* push a node onto expression stack, top two in stack are its children */
void push_node (char op) {
Node *n = new Node;
n->operation_ = op;
n->roperator_ = exps.front();
exps.pop_front();
n->loperator_ = exps.front();
exps.pop_front();
exps.push_front(n);
}
/*
* there is only one expression left on the stack, the one that was parsed
*/
void print_exp () {
Exp *e = exps.front();
exps.pop_front();
print_exp(e);
delete e;
}
The following routine can pretty print your expression tree:
以下例程可以漂亮地打印您的表达式树：
static void
print_exp (Exp *e, std::string ws = "", std::string prefix = "") {
Term *t = dynamic_cast<Term *>(e);
if (t) { std::cout << ws << prefix << t->n_ << std::endl; }
else {
Node *n = dynamic_cast<Node *>(e);
std::cout << ws << prefix << "'" << n->operation_ << "'" << std::endl;
if (prefix.size()) {
ws += (prefix[1] == '|' ? " |" : " ");
ws += " ";
}
print_exp(n->loperator_, ws, " |- ");
print_exp(n->roperator_, ws, " `- ");
}
}
回答by NTDLS
I wrote a class to handle this back in the day. It's a little verbose and perhaps not the most efficient thing on the planet but it handles signed/unsigned integers, double, float, logical and bitwise operations.
我写了一个类来处理这个问题。它有点冗长，也许不是地球上最有效的东西，但它处理有符号/无符号整数、双精度、浮点数、逻辑和按位运算。
It detects numeric overflow and underflow, returns descriptive text and error codes about syntax, can be forced to handle doubles as integers, or ignore signage, supports user definable precision and smart rounding and will even show its work if you set DebugMode(true).
它检测数字上溢和下溢，返回有关语法的描述性文本和错误代码，可以强制将双打作为整数处理，或忽略标志，支持用户可定义的精度和智能舍入，如果设置 DebugMode(true)，甚至会显示其工作。
Lastly...... it doesn't rely on any external libraries, so you can just drop it in.
最后......它不依赖任何外部库，因此您可以将其放入。
Sample usage:
示例用法：
CMathParser parser;
double dResult = 0;
int iResult = 0;
//Double math:
if (parser.Calculate("10 * 10 + (6 ^ 7) * (3.14)", &dResult) != CMathParser::ResultOk)
{
printf("Error in Formula: [%s].\n", parser.LastError()->Text);
}
printf("Double: %.4f\n", dResult);
//Logical math:
if (parser.Calculate("10 * 10 > 10 * 11", &iResult) != CMathParser::ResultOk)
{
printf("Error in Formula: [%s].\n", parser.LastError()->Text);
}
printf("Logical: %d\n", iResult);
The latest version is always available via the CMathParser GitHub Repository.
最新版本始终可通过CMathParser GitHub Repository 获得。
