We write Arithmetic expressions in following three notations –
Prefix Notation
In this notation, the operands are written after the operator. It is also known as Polish Notation.
For instance: +AB is a prefix expression.
Infix Notation
In this notation, the operators are written between the operands. It is similar to how we generally write an expression.
For instance: A + B is an infix expression.
Postfix Notation
In this notation, the operands are written before the operator. It is also known as Reverse Polish Notation.
For instance: AB+ is a postfix expression.
With the evaluation of these expressions, we can see the difference in results of (a+b)*c and a+(b*c).
Table of Contents
Rules for Arithmetic Expression Evaluation-
- Solve the Parenthesis first. In other words, firstly solve the sub-expressions inside the parenthesis. In the case of nested parenthesis, we begin from the innermost parenthesis.
- If an expression or sub-expression does not contain parenthesis, the expressions are solved according to the precedence of the operators. The precedence of 5 binary operators –
For Instance –
Let the expression = 4/2-[(5*3)+(abs(-7))]
Steps to solve the above expression –
- Firstly, we will solve the inner parenthesis i.e. (5*3) and (abs(-7)).
- After that, we solve the outer parenthesis i.e. addition of the results of inner parenthesis.
- After that, according to the precedence of the division operator above the subtraction operator, we will solve 4/2.
- Finally, we subtract the result of 4/2, and the above solved outer parenthesis.
Therefore, Result = -20
Example
Input : 4/2-[(5*3)+(abs(-7))]
Output : -20
Input : 100 * ( 2 + 12 )
Output : 1400
Algorithm for Arithmetic Expression Evaluation
- Initialize a string consisting of expression and two stacks for storing values and operators.
- Iterate from 0 to size of string – 1. Check if the character at the current index is equal to space, start the next iteration. If the character at the current index is equal to ‘(‘ insert it in operators stack.
- If the character at the current index is a digit. Check if there is a number following next to the digit, pick the whole number else if it is a single-digit pick the digit. Insert the digit/number in the value stack.
- Else if the character at the current index is ‘)’, iterate while the size of the operator’s stack is not zero and character at the current index is not equal to ‘(‘.
- After that, remove the 2 elements from the top of the value’s stack and 1 element from the operator stack.
- Apply the arithmetic operation on the two popped digits/numbers. Insert the answer in a values stack.
- Similarly, while the size of the operator’s stack is not zero, remove the 2 elements at the top of the value’s stack and an operator from operator stack.
- Apply the arithmetic operation on the two popped digits/numbers. Insert the answer in a values stack.
- Return the element at the top of the value stack.
C++ Program for Arithmetic Expression Evaluation
#include <bits/stdc++.h>
using namespace std;
int precedence(char op){
if(op == '+'||op == '-')
return 1;
if(op == '*'||op == '/')
return 2;
return 0;
}
int applyOp(int a, int b, char op){
switch(op){
case '+':
return a + b;
case '-':
return a - b;
case '*':
return a * b;
case '/':
return a / b;
}
}
int evaluate(string tokens){
int i;
stack <int> values;
stack <char> ops;
for(i = 0; i < tokens.length(); i++){
if(tokens[i] == ' ')
continue;
else if(tokens[i] == '('){
ops.push(tokens[i]);
}
else if(isdigit(tokens[i])){
int val = 0;
while(i < tokens.length() && isdigit(tokens[i])){
val = (val*10) + (tokens[i]-'0');
i++;
}
values.push(val);
}
else if(tokens[i] == ')'){
while(!ops.empty() && ops.top() != '('){
int val2 = values.top();
values.pop();
int val1 = values.top();
values.pop();
char op = ops.top();
ops.pop();
values.push(applyOp(val1, val2, op));
}
if(!ops.empty())
ops.pop();
}
else{
while(!ops.empty() && precedence(ops.top()) >= precedence(tokens[i])){
int val2 = values.top();
values.pop();
int val1 = values.top();
values.pop();
char op = ops.top();
ops.pop();
values.push(applyOp(val1, val2, op));
}
ops.push(tokens[i]);
}
}
while(!ops.empty()){
int val2 = values.top();
values.pop();
int val1 = values.top();
values.pop();
char op = ops.top();
ops.pop();
values.push(applyOp(val1, val2, op));
}
return values.top();
}
int main(){
cout << evaluate("4 / 2 - ( ( 5 * 3 ) + 7 )") << endl;
return 0;
}-20
Java Program for Arithmetic Expression Evaluation
import java.util.Stack;
class EvaluateString{
public static int evaluate(String expression){
char[] tokens = expression.toCharArray();
Stack<Integer> values = new Stack<Integer>();
Stack<Character> ops = new Stack<Character>();
for (int i = 0; i < tokens.length; i++){
if(tokens[i] == ' ')
continue;
if(tokens[i] >= '0' && tokens[i] <= '9'){
StringBuffer sbuf = new StringBuffer();
while(i < tokens.length && tokens[i] >= '0' && tokens[i] <= '9'){
sbuf.append(tokens[i++]);
}
values.push(Integer.parseInt(sbuf.toString()));
}
else if(tokens[i] == '(')
ops.push(tokens[i]);
else if(tokens[i] == ')'){
while (ops.peek() != '('){
values.push(applyOp(ops.pop(), values.pop(), values.pop()));
}
ops.pop();
}
else if(tokens[i] == '+' || tokens[i] == '-' || tokens[i] == '*' || tokens[i] == '/'){
while (!ops.empty() && hasPrecedence(tokens[i], ops.peek())){
values.push(applyOp(ops.pop(), values.pop(), values.pop()));
}
ops.push(tokens[i]);
}
}
while(!ops.empty()){
values.push(applyOp(ops.pop(), values.pop(), values.pop()));
}
return values.pop();
}
public static boolean hasPrecedence(char op1, char op2){
if (op2 == '(' || op2 == ')')
return false;
if ((op1 == '*' || op1 == '/') && (op2 == '+' || op2 == '-'))
return false;
else
return true;
}
public static int applyOp(char op, int b, int a){
switch (op){
case '+':
return a + b;
case '-':
return a - b;
case '*':
return a * b;
case '/':
if (b == 0)
throw new
UnsupportedOperationException("Cannot divide by zero");
return a / b;
}
return 0;
}
public static void main(String[] args){
System.out.println(EvaluateString.evaluate("4 / 2 - ( ( 5 * 3 ) + 7 )"));
}
}-20
Complexity Analysis for Arithmetic Expression Evaluation
Time Complexity: O(n) where n is the size of the given string s.
Space Complexity: O(n) because we used stack space for n elements.