c++ - Infix Calculator Expression Parser

Question

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<<'
';
        double result;
        if(evaluate(result, line)){
            cout<<result<<'
';
        }else{
            cout<<"Could not understand input

";
        }
    }
}

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

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.

The algorithm:

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.

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.

Stage 2: Now, Let's consider the following expression:

a) 2 + 3

this will be transformed into the following binary tree:

  +
 / 
2   3

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.

Stage 3: But for a more complex expression:

b) 2 * 3 + 4

The tree will be:

    +
   /  4
  *
 /  
2   3

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"
call method with "2*3"

and at this stage we fall back to "Stage 2" for the call ("2*3") and "Stage 1" for the call "4".

Stage 4: What if there are paranthesis in the expression? Such as

c) 2 * (3 + 4)

This will give us the tree:

      *
     / 
    2   +
       / 
      3   4

We modify the algorithm to be like:

• 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.

  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 https://sourceforge.net/p/nap-script/mercurial/ci/default/tree/compiler/interpreter.cpp . 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 1327.