OT: Arithmetic - Order of evaluating multiple divisions

A jokey question deserves a jokey answer.

This version does not require boost. It works by: - converting infix strings to postfix strings using shunting yard algorithm - converting postfix expression to list of tokens - builds AST bottom up from list of tokens - evaluates expression tree by performing postorder traversal.

g++ -o parse-crispies.exe parse-crispies.cc # For the Windows users :-) I always like to throw in the compile line.

#include <vector>

#include <cmath>

using namespace std;

template <class T>

class stack { private: vector<T> st; T sentinel; public: stack() { sentinel = T(); } bool empty() { return st.empty(); } void push(T info) { st.push_back(info); } T& top() { if (!st.empty()) { return st.back(); } return sentinel; } T pop() { T ret = top(); if (!st.empty()) st.pop_back(); return ret; } };

//determine associativity of operator, returns true if left, false if right bool leftAssociate(char c) { switch (c) { case '^': return false; case '*': return true; case '/': return true; case '%': return true; case '+': return true; case '-': return true; default: break; } return false; }

//determins precedence level of operator int precedence(char c) { switch (c) { case '^': return 7; case '*': return 5; case '/': return 5; case '%': return 5; case '+': return 3; case '-': return 3; default: break; } return 0; }

//converts infix expression string to postfix expression string string shuntingYard(string expr) { stack<char> ops; string output; for (char c : expr) { if (c == '(') { ops.push(c); } else if (c == '+' || c == '-' || c == '*' || c == '/' || c == '^' || c == '%') { if (precedence(c) < precedence(ops.top()) || (precedence(c) == precedence(ops.top()) && leftAssociate(c))) { output.push_back(' '); output.push_back(ops.pop()); output.push_back(' '); ops.push(c); } else { ops.push(c); output.push_back(' '); } } else if (c == ')') { while (!ops.empty()) { if (ops.top() != '(') { output.push_back(ops.pop()); } else { ops.pop(); break; } } } else { output.push_back(c); } } while (!ops.empty()) if (ops.top() != '(') output.push_back(ops.pop()); else ops.pop(); cout<<"Postfix: "<<output<<endl; return output; }

struct Token { int type; union { double num; char op; }; Token(double n) : type(0), num(n) { } Token(char c) : type(1), op(c) { } };

//converts postfix expression string to vector of tokens vector<Token> lex(string pfExpr) { vector<Token> tokens; for (int i = 0; i < pfExpr.size(); i++) { char c = pfExpr[i]; if (isdigit(c)) { string num; do { num.push_back(c); c = pfExpr[++i]; } while (i < pfExpr.size() && isdigit(c)); tokens.push_back(Token(stof(num))); i--; continue; } else if (c == '+' || c == '-' || c == '*' || c == '/' || c == '^' || c == '%') { tokens.push_back(Token(c)); } } return tokens; }

//structure used for nodes of expression tree struct node { Token token; node* left; node* right; node(Token tok) : token(tok), left(nullptr), right(nullptr) { } };

//builds expression tree from vector of tokens node* buildTree(vector<Token> tokens) { cout<<"Building Expression Tree: "<<endl; stack<node*> sf; for (int i = 0; i < tokens.size(); i++) { Token c = tokens[i]; if (c.type == 1) { node* x = new node(c); x->right = sf.pop(); x->left = sf.pop(); sf.push(x); cout<<"Push Operator Node: "<<sf.top()->token.op<<endl; } else if (c.type == 0) { sf.push(new node(c)); cout<<"Push Value Node: "<<c.num<<endl; continue; } } return sf.top(); }

//evaluate expression tree, while anotating steps being performed. int recd = 0; double eval(node* x) { recd++; if (x == nullptr) { recd--; return 0; } if (x->token.type == 0) { for (int i = 0; i < recd; i++) cout<<" "; cout<<"Value Node: "<<x->token.num<<endl; recd--; return x->token.num; } if (x->token.type == 1) { for (int i = 0; i < recd; i++) cout<<" "; cout<<"Operator Node: "<<x->token.op<<endl; double lhs = eval(x->left); double rhs = eval(x->right); for (int i = 0; i < recd; i++) cout<<" "; cout<<lhs<<" "<<x->token.op<<" "<<rhs<<endl; recd--; switch (x->token.op) { case '^': return pow(lhs, rhs); case '*': return lhs*rhs; case '/': if (rhs == 0) { cout<<"Error: divide by zero."<<endl; } else return lhs/rhs; case '%': return (int)lhs % (int)rhs; case '+': return lhs+rhs; case '-': return lhs-rhs; default: break; } } return 0; }

int main() { // string expr = "3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3"; string expr = "9 / 9 / 9 / 9"; // Your desired expression goes here

cout<<eval(buildTree(lex(shuntingYard(expr))))<<endl; return 0; }

$ parse-crispies.exe Postfix: 9 9 / 9 / 9/ Building Expression Tree: Push Value Node: 9 Push Value Node: 9 Push Operator Node: / Push Value Node: 9 Push Operator Node: / Push Value Node: 9 Push Operator Node: / Operator Node: / Operator Node: / Operator Node: / Value Node: 9 Value Node: 9 9 / 9 Value Node: 9 1 / 9 Value Node: 9 0.111111 / 9

Which is, roughly speaking, 1/81

What can I say, when the computer said it all :-)

Paul

Apart from the fact that "9 / 9 / 9 / 9" isn't the same as the question uses (*), this proves the point: it evaluates "9 / 9 / 9" as 0.111111 or

(*) The long line of a numerator / denominator fraction is executed last, not first, so you fully evaluate the numerator and the denominator, then evaluate the fraction.

I see that providing the program, was unintentionally a good idea.

As a thought experiment, pick up your calculator.

How many division symbols are on it ? [one]

Does the calculator have a "long horizontal line" and a "regular division" symbol ? [no]

There is no instantiation of a long horizontal line with magic properties, on computers.

There are only the rules of operator precedence.

If you, as a mathematician, wish to communicate with other mathematicians, then you use accepted notation, with accepted operator precedence.

In cases where there is the possibility of an ambiguity (such as drawing a long line, and wishing the audience to interpret it a certain way), then you have the option of adding additional symbols, so that there is no ambiguity about what you intend.

Now, pick up that computer program. The C++ program I provided (from Rosetta).

Go to the input line.

Craft an expression that the program will use to achieve the answer you want.

Now, go back to your Facebook diagram and add the missing two items to the drawing.

Then, surprise us.

It's (or variants thereof) everywhere. It's called a math puzzle, but it's a convention puzzle

Not quite always! On my Casio fx-991EX I can do this:

I was 13 when *Jonnie Roscoe* taught us to follow the convention BODMAS (brackets,oving,division,multiplication,addition,subtraction) I have never had reason to doubt him.

That is probably what everyone in Facebook uses.

Paul

FWIW LibreCalc and an old Excel both give 81 assuming it is parsed as

In message <gw2dne6pMaGFKa snipped-for-privacy@brightview.co.uk>, NY snipped-for-privacy@privacy.net writes

SMath Studio says 1

divide top and bottom by 9( iff 9 ne 0 )

------

the denominator reduces to

---------

general case

f(x) = x/x/x/x

simplifies to x iff x ne 0

Brian

Reverse Polish gives 1

there are 3 operators and 4 numbers

Or maybe my calculator is totally Hewlett.

The long line is an implied parenthesis (magical property),so the answer is 81

Compare

-----------

Enuf arith for the day.

Brian

That's exactly what the Casios do.

When you create the template for entering a fraction it effectively creates

( xxx ) / ( yyy )

which displays as the long line with holding marks above and below and then fills in xxx and yyy as two separate expressions as you edit them.

nib