中缀计算器表达式解析器 [英] Infix Calculator Expression Parser
问题描述
如何解析和计算中缀计算器语法中的表达式？我想到了两种方式。
How do I parse and evaluate expressions in an infix calculator grammar? I thought of two ways.
第一个涉及使用两个堆栈。一个是数字，另一个是操作符，我将评估运算符的优先级和关联，以便找出如何评估表达式。
The 1st involves using two stacks. One is for numbers and the other is for operators, and I would assess the operator precedence and association in order to figure out how to evaluate an expression.
第二种方法涉及将中缀表达式转换为后缀，我不知道我该怎么做。这只是一个想法。目前我设置我的程序，打算使用第一种方法。
The second method involves converting the infix expression to postfix which I have no idea how I'd go about doing. It was just an idea. Currently I set up my program with the intention to use the 1st method.
#include <iostream>
#include <string>
#include <sstream>
using namespace std;
bool die(const string &msg);
//stack class
class Stack{
public:
Stack();
void push(const double &val);
void push(const string &oper);
double popnum();
string popop();
double getopele();
double getnumele();
private:
static const unsigned MAX=30;
string opstack[MAX];
double numstack[MAX];
unsigned opele;
unsigned numele;
};
//operator type
struct OP{
string name;
void * func;
unsigned arity;
unsigned prec;
bool lass;
string descrip;
};
//operator table
OP op[]={{"+", add, 2, 4, true, "2+3 is 5"},
{"-", subtract, 2, 4, true, "2-3 is -1"},
{"*", multiply, 2, 6, true, "2*3 is 6"},
{"/", divide, 2, 6, true, "2/3 is 0.666666..., div by 0 illegal"}};
unsigned OPELE =sizeof(op)/sizeof(op[0]);
//operators
bool add(double &r, double &x, double &y);
bool subtract(double &r, double &x, double &y);
bool multiply(double &r, double &x, double &y);
bool divide(double &r, double &x, double &y);
//Manip
unsigned findindex(string token, OP op[], unsigned OPELE);
bool parse(double &t, const string &token);
bool evaluate(double &result, string line);
bool weird(double x);
int main(){
for(string line; getline(cin, line);){
if(line=="QUIT") break;
if(line.empty()) continue;
if(line=="DOC")
for(unsigned i=0; i<OPELE; i++)
cout<<op[i].name<<" | "<<op[i].descrip<<'\n';
double result;
if(evaluate(result, line)){
cout<<result<<'\n';
}else{
cout<<"Could not understand input\n\n";
}
}
}
Stack::Stack(){
opele=0;
numele=0;
}
void Stack::push(const double &val){
if(MAX) die("Stack Overflow");
numstack[numele++]=val;
}
void Stack::push(const string &oper){
if(MAX) die("Stack Overflow");
opstack[opele++]=oper;
}
double Stack::popnum(){
if(!numele) die("Stack Underflow");
return numstack[--numele];
}
string Stack::popop(){
if(!opele) die("Stack Underflow");
return opstack[--opele];
}
double Stack::getopele(){
return opele;
}
double Stack::getnumele(){
return numele;
}
bool add(double &r, double &x, double &y){
double t = x + y;
if( weird(t) ) return false;
r = t;
return true;
}
bool subtract(double &r, double &x, double &y){
double t = x - y;
if( weird(t) ) return false;
result = t;
return true;
}
bool multiply( double & r, double& x, double &y ){
double t = x * y;
if( weird(t) ) return false;
result = t;
return true;
}
bool divide( double & result, double &x, double &y ){
double t = x / y;
if( weird(t) ) return false;
result = t;
return true;
}
unsigned findindex(string token, OP op[], unsigned OPELE){
for(unsigned i=0l i<OPELE; i++)
if(op[i].name==token)
return i;
return UINT_MAX;
}
bool parse(double &t, const string &token){
istringstream sin( token );
double t;
if( !(sin >>t) ) return false;
char junk;
if( sin >>junk ) return false;
value = t;
return true;
}
bool evaluate(double &result, string line){
istringstream sin(line);
Stack s;
for(string token; sin>>token;){
double t;
if(parse(t, token)){
s.push(t);
}else if(
}
}
bool weird( double x ){
return x != x || x != 0 && x == 2*x;
}
推荐答案
这将是一个长的读，但无论如何，我会与你分享我用来解析一个中缀表达式的算法，并将其存储为一个二叉树。不是堆栈，但二叉树。解析，将给后缀顺序。
This will be a long read, but anyway, I will share with you the algorithm I use to parse an infix expression and store it as a binary tree. Not Stack, but binary tree. Parsing that will give the postfix order easily. I don't say this is the best algorithm out there, but this works for my scripting language.
算法：
我们有一个对二进制树的当前节点和当前表达式进行操作的方法。节点包含一个data字段和一个type字段。
We have a method which operates on a "current node" of a binary tree and a "current expression". The nodes contain a "data" field and a "type" field.
阶段1：简单的事情，例如4直接进入节点，我们指定类型为DATA，即使用这个信息。
Stage 1: Simple things, such as "4" go directly into the node, and we specify the type to be as "DATA", ie. use this information as it is.
阶段2：现在，让我们考虑下面的表达式：
Stage 2: Now, Let's consider the following expression:
a) 2 + 3
这将被转换为以下二叉树：
this will be transformed into the following binary tree:
+
/ \
2 3
所以，运算符进入节点，操作数进入叶子。将表达式a）转换为树很简单：找到运算符，放入树的当前节点，指定要作为运算符PLUS的节点的类型，并且剩下的是什么进入树到节点的左边部分，什么是右边进入正确的树。尼斯和简单，使用阶段1的信息，两个叶子将是值为2和3的DATA叶。
So, the operators go into the nodes and the operands go into the leafs. Transofrming the expression a) into the tree is pretty simple: find the operator, put in the "current" node of the tree, specify the type of the node to be operator "PLUS", and what is left of it goes into the tree to the left part of the node, what is right of it goes into the right tree. Nice and simple, using the information from Stage 1 the two leafs will be "DATA" leafs with value 2 and 3.
阶段3：但是对于更复杂的表达式：
Stage 3: But for a more complex expression:
b) 2 * 3 + 4
树将是：
+
/ \ 4
*
/ \
2 3
上面的算法如下：找到具有最高优先级的第一个运算符（考虑c ++准则... +（加号）和 - （减号）的优先级为6，而优先级为*（乘法），/ ％（modulo）为5），将表达式分为两部分（在具有最高优先级的操作数之前和具有最高优先级的操作数之后），并递归调用两个部分的方法，同时将具有最高优先级的运算符放入当前节点。所以，我们创建一个像hdata的树：
So we need to modify the algorithm above to the following: Find the first operator which has the highest precedence (considering c++ guidelines... precedence of + (plus) and - (minus) is 6, while precedence of * (multiply), / (divide) and % (modulo) is 5) in the expression, divide the expression into two parts (before operand with highest precedence and after operand with highest precedence) and call recursively the method for the two parts, while placing the operator with the highest precedence into the current node. So, we do create a tree wit hdata like:
+
/ \
/ call method with "4"
使用2 * 3的呼叫方法
call method with "2*3"
，在这个阶段我们回到阶段2为呼叫（2 * 3）和阶段1为呼叫4。
and at this stage we fall back to "Stage 2" for the call ("2*3") and "Stage 1" for the call "4".
阶段4：如果表达式中有句法会怎么样？如
Stage 4: What if there are paranthesis in the expression? Such as
c) 2 * (3 + 4)
这将给我们树：
*
/ \
2 +
/ \
3 4
我们将算法修改为：
- 当前表达式包含在一个句子中，从中删除该句子并重新启动算法。小心。 （2 + 3 * 4 + 5）被认为被包围在一个句子中，而（2 + 3）*（4 + 5）是非。所以，它不只是表达式的开始和结束字符，但你有效地需要计数parantheses。 （这是一种递归方法，不要害怕第一步...）
-
现在找到第一个运算符，它在表达式的括号之外具有最高优先级。再次，采取表达式的左侧和右侧，并再次调用该方法，直到你最终在阶段1ie。与单个数据元素。
- while the current expression is enclosed in a paranthesis remove the paranthesis from it and restart the algorithm. Be careful. (2 + 3 * 4 + 5) is considered to be enclosed in a parnethesis while (2+3)*(4+5) is NOT. So, it's not just the starting and ending characters of the expression, but you effectively need to count the parantheses. (this is a recursive method, don't be afraid of the first step...)
now find the first operator with the highest precedence outside the parantheses of the expression. Again, take the left and right sides of the expression and call the method again and again till you end up at "Stage 1" ie. with a single data element.
现在，这是一个由普通数字和运算符组成的表达式的算法。对于更复杂的信息，您可能需要对其进行优化以满足您的需要。如果您认为值得，请查看 http://nap-script.cvs.sourceforge.net/viewvc/nap-script/nap/interpreter.cpp?view=markup 。这包含了上面关于更复杂概念（变量，方法调用，后缀/前缀操作符等）的算法的完整实现（在C中）。方法是build_expr_tree，从第982行开始。
Now this is an algorithm for an expression which consists of plain numbers and operators. For more complex information you might need to refine it to suit your needs. If you consider it worth, take a look at http://nap-script.cvs.sourceforge.net/viewvc/nap-script/nap/interpreter.cpp?view=markup . This contains a full implementation (in C) of the algorithm above with regard to more complex notions (variables, method calls, postfix/prefix operators, etc...) The method is build_expr_tree, starts at line 982.
这篇关于中缀计算器表达式解析器的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
