Calculator precedence

[adam2016]

Hi guys,

long time no post, any how I'm just doing some revision and re reading Bjarnes practices and principles, in chapter 6 we make a token calculator, we tokenize so we can implement correct mathematic precedence ie multiplication and division before addition and subtraction,

I understand the gist of the code and have no problems implementing it, it uses recursion and while loops to keep testing for operators,

any how what I don't get is... I noticed that when tracing the program with various number of examples addition will actually be done before multiplication in some cases BUT we will always get the right answer!! that makes me scratch my head a little bit, so lets look at an example

2 + 2 + 2 + 2 * 3 + 2 + 2

this answer will obviously equal 16, and I test the calculator and it gives the correct result, 16.

but when following the program we first let left be equal to term(), we call term which returns a 2 so left equals 2, we then check for an operator and in this case it is a + so we then += left to term again, so yet again we call term(), and yet again term returns 2 so now left(2) is += with 2 which equals 4, but have you noticed addition has been done before multiplication!!! technically aren't we breaking the rules?? since we are adding before we hit the multiplication operation???

the program gives the right answer though every time I test it and no matter how long the expression is, can anybody help explain this and why it's ok to do addition in this case before multiplication??

thanks

#include <iostream>

using namespace std;

class Token{

 public:
     char type;
     int value;

     Token(){

        type = '0';
        value = 0;
     }

     Token(int value):value(value){

        type = '8';
     }
     Token(char type,int value): type(type),value(value){}

};

class TokenStream{
public:
    Token buffer;
    bool bufferFull;

    TokenStream()
    {

        buffer = NULL;
        bufferFull = false;

    }

    Token getToken()
    {
        if(bufferFull)
        {
            bufferFull = false;
            return buffer;
        }

        char c;
        cin >> c;

        switch(c){

    case ';':
    case '+':
    case '-':
    case '*':
    case '/':
    case 'q':
        return Token(c,0);
    case '1':
    case '2':
    case '3':
    case '4':
    case '5':
    case '6':
    case '7':
    case '8':
    case '9':
    case '10':
        {
            cin.putback(c);
            int val = 0;
            cin >> val;
            return Token(val);
        }
    default:
        cout << "bad token" << endl;

        }
    }

    void putBack(Token t){

      if(bufferFull){

         return;
      }
      buffer = t;
      bufferFull = true;

    }

};

TokenStream ts;

double primary(){

  Token t = ts.getToken();

  switch(t.type){

   case '8':
       return t.value;
   case '0':
        return t.type;
   default:
       cout << "error" << endl;
  }

}

double term(){

  double left = primary();
  Token t = ts.getToken();

  while(true){
        switch(t.type)
        {

        case '*':
        {
            left *= primary();
            t = ts.getToken();
        }
        break;
        case '/':{
            left /= primary();
            t = ts.getToken();
        }
        break;
        default:
            ts.putBack(t);
            return left;
    }
  }
}

double expression(){

   double left = term();
   Token t = ts.getToken();

   while(true){

        switch(t.type)
        {

        case '+':
        {
            left += term();
            t = ts.getToken();
        }
        break;
        case '-':
        {
            left -= term();
            t = ts.getToken();
        }
        break;
        default:
            ts.putBack(t);
            return left;
        }
   }
}


int main()
{

    int result = 0;

    while(true){
       cout << "enter expression" << endl;
       Token quit = ts.getToken();
       if(quit.type == 'q'){

          break;
       }
       ts.putBack(quit);

       result = expression();
    }

    cout << result << endl;
}

[dutch]

You're confusing "operator precedence" with "order of evaluation". They are related but not the same thing.

The fact that multiplication has a higher precedence than addition simply tells us that there are invisible parentheses around 2 * 3. It tells what goes with what in the absence of explicit parentheses. It doesn't dictate the total order that you do things.

Without the precedence rules we would presumably just do things from left to right and end up with 8 * 3 by the time we hit the multiplication, which would give a different result of 28, i.e., (2 + 2 + 2 + 2) * 3 + 2 + 2.

But the precedence rules tell us it should be interpreted like this: 2 + 2 + 2 + (2 * 3) + 2 + 2. Or, fully parenthesized including associativity rules: (((((2 + 2) + 2) + (2 * 3)) + 2) + 2).

Or as a parse tree:

(((((2 + 2) + 2) + (2 * 3)) + 2) + 2).
                                 +
                            +      2
                 +            2
            +         *
       +      2     2   3
     2   2

Note that the leftmost 2+2 is actually "deepest" in the tree (but it wouldn't need to be calculated first).

[adam2016]

ah ok I got you, basically the program may add 2 + 2 + 2 first but this will have no affect on the outcome as it will still give the correct result, I may need to elaborate...

2 will equal left, we now check if there is a multiplication operation to be done if so we do the multiplication first but there is not there is a +, again we check the the operator after the next number it is a plus again so it's safe to return 2, 2 + 2 are added to equal 4, again we check the next operator which is a + we call term again to check if the next operator after this + is a * and it's not so we return 2 yet again and add 2 to 4 which gives 6 , we then check the next operation which mentioned previously is a +, we then += term again and find that this time there is a * so we multiply 2 * 3 , next we check for another * but there is none so we return 6 , 6 is added to 6 which gives 12, after this we check the next operation which is a + we again call term and += it to left, term tells us there is no more * signs so we return 2, 12 is added to 2 which equals 14, again we get the next operation which is a + we check for any more *'s but none exist so we return 2, left(14) is added to 2 which gives 16, so 16 is the final result.

Again reading the above seems quite cryptic as I probably gave a horrid explanation but I do understand now :)

thanks Dutch!

[dutch]

I tried to make what I felt was simpler code.

#include <iostream>
#include <iomanip>
#include <sstream>
#include <string>
#include <stdexcept>
#include <cctype>

double expr(std::istream& in);

double primary(std::istream& in) {
    char ch;
    in >> ch;
    double val = 0.0;
    if (ch == '(') {
        val = expr(in);
        in >> ch;
        if (ch != ')')
            throw std::invalid_argument("missing closing paren");
    }
    else if (isdigit(ch) || ch == '-' || ch == '+') {
        in.unget();
        if (!(in >> val))
            throw std::invalid_argument("bad value");
    }
    else
        throw std::invalid_argument("bad value");
    return val;
}

double term(std::istream& in) {
    double val = primary(in);
    for (;;) {
        char ch;
        if (!(in >> ch))
            break;
        if (ch == '*')
            val *= primary(in);
        else if (ch == '/')
            val /= primary(in);
        else {
            in.unget();
            break;
        }
    }
    return val;
}

double expr(std::istream& in) {
    double val = term(in);
    for (;;) {
        char ch;
        if (!(in >> ch))
            break;
        if (ch == '+')
            val += term(in);
        else if (ch == '-')
            val -= term(in);
        else {
            in.unget();
            break;
        }
    }
    return val;
}

int main() {
    std::string line;
    while (std::getline(std::cin, line)) {
        std::istringstream sin(line);
        try {
            std::cout << "    " << expr(sin) << '\n';
        } catch (std::invalid_argument& e) {
            std::cerr << "error: " << e.what() << '\n';
        }
    }
}

[Emil Enchev]

@dutch

ok...

2*((-2))
    -4

but...

2*(-(-2))
error: bad value

Do you know how to deal with it?

It have simple solution. For example, some calculators add 0 in front of "-" and make from 2*(-(-2)) this...

2*(0-(0-2))
    4

[Emil Enchev]

adam2016 , I don't understand logic yet, because I'm new in C++, but is this correct

case '10'

or you intended to do

case '0'?

Your code don't work for me at all.

68:10: warning: multi-character character constant [-Wmultichar]
 In constructor 'TokenStream::TokenStream()':
34:16: warning: passing NULL to non-pointer argument 1 of 'Token::Token(int)' [-Wconversion-null]
 In member function 'Token TokenStream::getToken()':
68:10: warning: case label value exceeds maximum value for type
 In function 'double primary()':
110:1: warning: control reaches end of non-void function [-Wreturn-type]
 In member function 'Token TokenStream::getToken()':
79:5: warning: control reaches end of non-void function [-Wreturn-type

the program gives the right answer though every time I test it and no matter how long the expression is, can anybody help explain this and why it's ok to do addition in this case before multiplication??

So show me first how it works for addition.

By the way: Don't use "Programming: Principles and Practice Using C++" as Introductory first book for C++. Bjarne Stroustrup CAN'T make Intro C++ books. I even think he can not make a nice C ++ language, and he is one of the reasons why this language is so complicated for many people. The head of a confused person can only give birth to confused things. Do not bother with him until you start to understand the language very well.

[dutch]

Emil Enchev wrote:

Do you know how to deal with it?

Good point. The fix is quite simple (changes are lines 80-82 below).

I also added a constant table (pi, e) and some single-argument functions (sqrt, log).
And a trace function activated with the -t flag.

This is still pretty basic.
* Variables could be added.
* The functions could be extended to those with more than one argument.

Example output:

(1 + sqrt(5)) / 2    
expr
    term
        primary
            expr
                term
                    primary
                    1
                1
                term
                    primary
                        expr
                            term
                                primary
                                5
                            5
                    2.23607
                3.23607
        3.23607
        primary
        1.61803
    1.61803
1.61803

#include <iostream>
#include <iomanip>
#include <sstream>
#include <string>
#include <map>
#include <stdexcept>
#include <cctype>
#include <cmath>

const int TabSize = 4;
int level = 0;
bool trace = false;

void prn(const std::string& msg) {
    if (trace)
        std::cout << std::setw(level * TabSize) << "" << msg << '\n';
}

void prn(double val) {
    if (trace)
        std::cout << std::setw(level * TabSize) << "" << val << '\n';
}

void enter(const std::string& msg) {
    prn(msg);
    ++level;
}

void leave() {
    --level;
}

using Func = double (*) (double);

std::map<std::string, std::pair<double, Func>> symbols {
    // Constants:
    { "pi",      { 2 * acos(0)      , nullptr } },
    { "e",       { exp(1)           , nullptr } },
    { "golden",  { (1 + sqrt(5)) / 2, nullptr } },

    // Functions:
    { "sqrt",   { 0, sqrt } },
    { "log",    { 0, log  } }
};

double expr(std::istream& in);

std::string get_identifier(std::istream& in) {
    std::string identifier;
    char ch;
    while (in.get(ch) && (isalpha(ch) || isdigit(ch) || ch == '_'))
        identifier.push_back(ch);
    if (in) in.unget();
    return identifier;
}

double run_function(std::istream& in, Func func) {
    char ch;
    in >> ch;
    if (ch != '(')
        throw std::invalid_argument("missing ( after function name");
    double val = func(expr(in));
    in >> ch;
    if (ch != ')')
        throw std::invalid_argument("missing ) after function arg");
    return val;
}

double primary(std::istream& in) {
    enter("primary");
    char ch;
    in >> ch;
    double val = 0.0;
    if (ch == '(') {    
        val = expr(in);
        in >> ch;
        if (ch != ')')
            throw std::invalid_argument("missing )");
    }
    else if (ch == '-' || ch == '+')
        val = ch == '-' ? -expr(in) : expr(in);
    else if (isdigit(ch)) {
        in.unget();
        if (!(in >> val))
            throw std::invalid_argument("bad value");
    }
    else if (isalpha(ch)) {
        in.unget();
        std::string variable = get_identifier(in);

        auto it = symbols.find(variable);
        if (it == symbols.end())
            throw std::invalid_argument("unknown variable");

        if (!it->second.second)       // null function ptr
            val = it->second.first;        // get variable's value
        else                          // else it's a function
            val = run_function(in, it->second.second);
    }
    else
        throw std::invalid_argument("bad value");
    leave();
    return val;
}

double term(std::istream& in) {
    enter("term");
    double val = primary(in);
    for (;;) {
        prn(val);
        char ch;
        if (!(in >> ch) || ch == ';')
            break;
        if (ch == '*')
            val *= primary(in);
        else if (ch == '/')
            val /= primary(in);
        else {
            in.unget();
            break;
        }
    }
    leave();
    return val;
}

double expr(std::istream& in) {
    enter("expr");
    double val = term(in);
    for (;;) {
        prn(val);
        char ch;
        if (!(in >> ch) || ch == ';')
            break;
        if (ch == '+')
            val += term(in);
        else if (ch == '-')
            val -= term(in);
        else {
            in.unget();
            break;
        }
    }
    leave();
    return val;
}

int main(int argc, char **argv) {
    if (argc == 2 && std::string(argv[1]) == "-t")
        trace = true;
    std::string line;
    while (std::getline(std::cin, line)) {
        std::istringstream sin(line);
        if (line.find_first_not_of(" \t\n\r\v\f") == line.npos)
            continue; // blank line
        try {
            while (sin) {
                level = 0;
                if (!trace) std::cout << "    ";
                std::cout << expr(sin) << "\n";
                if (trace) std::cout << '\n';
            }
        } catch (std::invalid_argument& e) {
            std::cerr << e.what() << '\n';
        }
    }
}

[adam2016]

adam2016 , I don't understand logic yet, because I'm new in C++, but is this correct

case '10'

or you intended to do

case '0'?

Your code don't work for me at all.

that may be a little confusing but in this case I use the case '0' to indicate a number and the case '8' to represent a operator, the code should work though.

Also I like the revamped code Dutch, adds a lot more functionality and is tidied up significantly, I have to agree Bjarne although one of the creators of C++ and an elite programmer is not the best teacher.