Implement BODMAS using C++.














































Implement BODMAS using C++.



(Pre-requisite : Basic C++, STL stack)

What is BODMAS ?

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.

BODMAS : refers to Bracket Open, Division, Multiplication, Addition, Subtraction, in the decreasing order of precedence.

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.

Infix Expression - The expression is in the form of (operand1 operator operand2), i.e. Binary Operator lies in between two of its operands.

Postfix Expression - The expression is in the form of (operand1 operand2 operator), i.e. Binary Operator lies after two of its operands.

NOTE - There also exist a prefix expression form, but i.e. out of the scope of this article.

Algorithm1 : for converting Infix to Postfix :

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

Algorithm2 : for evaluating our resulting postfix expression :

  1. Scan the list formed in the Algorithm1 from left to right.
  2. create a new stack (let's say stack1)
  3. If the current item is a operand
    1. Push in the stack1
  4. else :
    1. 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..
    2. push the result we get in stack1 again.
  5. 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.)


Comments