It is a rule to evaluate a given mathematical expression, It follows the order of precedence of operator evaluation, How? Let's see -

Take the below example -

The result of the above expression comes, from the fact that, division has more precedence than addition, so division is evaluated first.

Though in computer science we refer the precedence of** Multiplication** and **division** as same, and precedence of **Addition** and **Subtraction** as same.

The way we are going to implement BODMAS in C++, is how somewhat different, we need to take the help of a Data Structure, particularly the **STACK** data structure, which follows, LIFO rule which will help us in designing our algorithm.

In particularly we will implement the BODMAS with the help of conversion from **Infix **to **Postfix conversion.**

*Scan the Infix expression from left to write.**If current character is a operand, save it in a list.**else**if the precedence of current operator is greater than, operators we have seen so far, than push it in our stack.**else pop from stack until the we reach to our sentinel character/ stack becomes empty, and add to the list.**push current operator to the stack.**Perform above steps until reached the end of the expression.**Pop out all operators from the sack and add it to the list.*

*Scan the list formed in the Algorithm1 from left to right.**create a new stack (let's say stack1)**If the current item is a operand**Push in the stack1**else :**pop two items from stack1 and store it in some temporary variables, and evaluate the result, according the operator, we have received, i.e. for '+' perform addition, etc..**push the result we get in stack1 again.**return stack1's top value*

Below is the basic implementation of the above algorithms

(I equivocally commented the program)

#include<bits/stdc++.h> using namespace std; #define ll long long /* The program doesn't handle the unbalanced parantheses, that logic can be create easily with stacks, and it is exercise */ // Precedence of basic operators int precedence(char operate) { if (operate == '+' || operate == '-') return 1; else if (operate == '*' || operate == '/') return 2; else if (operate == '^') return 3; return 0; } // utility to find if character is a operand. bool isOperand(char x) { if (x == '+' || x == '-' || x == '*' || x == '/' || x == '(' || x == ')' || x == '^') return false; return true; } // Algorithm1 // Utility to create Postfix expression vector<string> InfixtoPostfix(string s) { string string_without_spaces{}; // Creating a string that doesn't include spaces // (it is not mandatory, but will decrease the efforts in further steps). for (auto x : s) if (x != ' ') string_without_spaces += x; int length = string_without_spaces.size(); stack<char> Operators; // It will store our operators Operators.push('#'); // '#' will act as a sentinel, to avoid collision with empty stack /* result will store our Postfix expression, where each value in result, is either an operator, or an operand. */ vector<string> result; int i = 0, j = 0; while (i < length) { // If Operand, we find the full number starting at index i if (isOperand(string_without_spaces[i])) { string this_number{}; while (i < string_without_spaces.size() && isOperand(string_without_spaces[i])) this_number += string_without_spaces[i++]; result.push_back(this_number); } // If the Current character is '(', we simply push else if (string_without_spaces[i] == '(') Operators.push(s[i++]); /* If the current character is ')', we get all operators occuring before the character '('. */ else if (string_without_spaces[i] == ')') { while (Operators.top() != '#' && Operators.top() != '(') { result.push_back(string(1, Operators.top())); Operators.pop(); } if (Operators.top() == '(') Operators.pop(); i++; } // If the current character is a operator, we find it's appropriate place. else { string temporary{}; while (Operators.top() != '#' && precedence(Operators.top()) >= precedence(string_without_spaces[i])) { temporary = string(1, Operators.top()); result.push_back(temporary); Operators.pop(); } Operators.push(s[i++]); } } // If there are still some operators left, we simply get those operators. while (Operators.top() != '#') { result.push_back((Operators.top() == '^' ? "^" : string(1, Operators.top()))); Operators.pop(); } // Just return our result. return result; } // Algorithm2 // Utility to calculate the value Postfix expression we found long long evaluate(vector<string> &postfix) { int i = 0; stack<string> values; cout << postfix.size() << endl; while (i < postfix.size()) { // We know operator will have size 1, but to avoid collision with numbers (with number of digits 1) // I anded our basic condition with one more condition i.e. isoperand. if (postfix[i].size() == 1 && !isOperand(postfix[i][0])) { ll number1 = stoll(values.top(), nullptr, 10); // Second operand (for binary opeartor) values.pop(); ll number2 = stoll(values.top(), nullptr, 10); // First Operand (for binary operator) values.pop(); ll result = 0; // Our cases for operands switch (postfix[i][0]) { case '+': result = number2 + number1; break; case '-': result = number2 - number1; break; case '/': result = number2 / number1; break; case '*': result = number2 * number1; break; case '^': result = (ll)pow(number2, number1); break; default: break; } // Pushing the result back to stackafter performing binary operation. values.push(to_string(result)); } else values.push(postfix[i]); i++; } return stoll(values.top(), nullptr, 10); } // Example program to verify our int main() { string exp = "18^2-12^4"; cout << exp << endl; auto postfix = InfixtoPostfix(exp); for (auto x : postfix) cout << x << " "; cout << endl; auto result = evaluate(postfix); cout << "Our result is : " << result << endl; }

*(As a homework, try to implement a utility which check for balanced parentheses before converting it to infix.)*

Name | Views | Likes |
---|---|---|

C++ program to find Minimum of each subarrays in Linear Time. | 53 | 0 |

C++ Algorithm to find Path matrix of a graph. | 48 | 0 |

Implement BODMAS using C++. | 161 | 0 |

Shell Sort. | 221 | 0 |

3n+1 Problem Solution using C++. | 84 | 0 |

## Comments