中缀计算器表达解析器

Question

如何在中缀计算器语法中解析和计算表达式？我想到了两种方式.

第一个涉及使用两个堆栈.一个是数字,另一个是运算符,我会评估运算符的优先级和关联,以便弄清楚如何计算表达式.

第二种方法涉及将中缀表达式转换为后缀,我不知道我该怎么做.这只是一个想法.目前我设置我的程序是为了使用第一种方法.

#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;
}

Answer 1

这将是一个很长的阅读,但无论如何,我将与您分享我用来解析中缀表达式并将其存储为二叉树的算法.不是堆栈,而是二叉树.解析将轻松给出后缀顺序.我不是说这是最好的算法,但这适用于我的脚本语言.

算法:

我们有一种方法,它对二叉树的"当前节点"和"当前表达式"进行操作.节点包含"数据"字段和"类型"字段.

阶段1:简单的事情,例如"4"直接进入节点,我们将类型指定为"DATA",即.按原样使用此信息.

第2阶段:现在,让我们考虑以下表达式:

a) 2 + 3

这将转换为以下二叉树:

  +
 / \
2   3

因此,运算符进入节点,操作数进入叶子.将表达式a)转换到树中非常简单:找到运算符,放入树的"当前"节点,指定节点的类型为运算符"PLUS",剩下的内容将进入树中在节点的左侧部分,它的右侧是否进入右侧树.很好很简单,使用第1阶段的信息,两个叶子将是"DATA"叶子,值为2和3.

第3阶段:但是对于更复杂的表达:

b) 2 * 3 + 4

树将是:

    +
   / \ 4
  *
 / \ 
2   3

因此,我们需要将上面的算法修改为以下内容:找到具有最高优先级的第一个运算符(考虑c ++指南... +(加号)和 - (减号)的优先级为6,而*(乘法)的优先级, /(除)和%(modulo)是5)在表达式中,将表达式分为两部分(在具有最高优先级的操作数之前和具有最高优先级的操作数之后)并递归调用这两部分的方法,同时将运算符与当前节点的最高优先级.所以,我们用hdata创建一个树,如:

    +
   / \ 
  /  call method with "4"
call method with "2*3"

在这个阶段,我们回到呼叫"4"的呼叫("2*3")和"阶段1"的"阶段2".

第四阶段:如果表达中有副词,该怎么办？如

c) 2 * (3 + 4)

这将给我们树:

      *
     / \
    2   +
       / \
      3   4

我们将算法修改为:

• 当前表达式括在一个paranthesis中删除它的paranthesis并重新启动算法.小心.(2 + 3*4 + 5)被认为包含在一个parnethesis中,而(2 + 3)*(4 + 5)不是.所以,它不仅仅是表达式的起始和结束字符,而且你实际上需要计算这些parantheses.(这是一种递归方法,不要害怕第一步......)

• 现在找到第一个在表达式的parantheses之外具有最高优先级的运算符.再次,取表达式的左侧和右侧,并一次又一次地调用该方法,直到您最终到达"阶段1"即.使用单个数据元素.

  现在,这是一个由纯数和运算符组成的表达式算法.有关更复杂的信息,您可能需要对其进行优化以满足您的需求.如果您认为值得,请查看https://sourceforge.net/p/nap-script/mercurial/ci/default/tree/compiler/interpreter.cpp.这包含上面算法的完整实现(在C中)关于更复杂的概念(变量,方法调用,后缀/前缀运算符等等).方法是build_expr_tree,从第1327行开始.