Last Updated on September 15, 2022 by Gokul Kannan
Problem Statement
You will be given a string representing a mathematical expression. You have to evaluate it and return the result.
Some Constraints
The input string will be in Infix Notation.
There will only be 4 operators: + – * /
There can be brackets present in the string. Only round brackets will be present i.e. ()
There can be spaces between the operators, operands, or brackets. It is not necessary that there will be just a single space only. So, you have to handle that as well.
We have numeric values as numbers and not any variables (like a,b,c, or x,y,z). So, apart from the numbers and operators, all other characters are invalid and will not be present in the string.
Examples
Note: Please note that you also have to maintain the general associativity order of arithmetic operators in case of same precedence.
Operator Precedence Rules
- The multiply (*) and divide (/) operators have equal precedence.
- The plus (+) and minus (-) operators have equal precedence.
- The precedence of multiply and divide operators is greater than the precedence of plus and minus operators.
- The part of the expression inside a pair of brackets must be evaluated first before anything in the complete expression.
As in the above example, even though the precedence of + is lower than that of *, since it is inside the brackets, it is evaluated first.
- The innermost pair of brackets must be evaluated first.
The above image shows the order of evaluation of brackets.
- If the precedence of operators is same and they are at the same level of evaluation then, the associativity comes into picture.
Associativity of Arithmetic Operators
So, we have seen the precedence rules and know that the precedence of some operators is equal to each other. For instance, the precedence of multiply and divide operators is the same. Similarly, the precedence of the plus and minus operators is the same. So, to evaluate an expression in such condition associativity comes into the picture. Have a look at the expression shown below.
In this expression, the plus and multiply operator have different precedence. So, it is clear that multiplication will occur first and then the addition and hence the result will be 2*3=6 + 5 = 11.
However, consider the expression shown below.
Here, multiply and divide operators have the same precedence. Solving multiplication first will give us the answer 5 4 = 20 / 3 = 6.
However, if we divide first, then the answer would be 4/3 = 1 and 51 = 6.
This produces a dilemma. However, the solution is simple.
The associativity of arithmetic operators is from left to right.
Hence, in case of operators having same precedence, the one on the left in the expression will be evaluated first.
Approach (Shunting Yard Algorithm)
So, this is a pre-devised algorithm that we need to follow for expression evaluation. So, let us see the rules first, and then, we will perform a dry run on one example.
Algorithm
We will use 2 stacks. One stack will contain the operands and another stack will contain operators. The operand stack will be an integer stack and the operator stack will be a stack of characters.
-
Get the current token/character of the expression.
-
If the current character is
a. A number, like 0, 10 154, 1023, etc, push it into the operand stack. Note one important point that the number is a string and we have to convert it into an integer for pushing it into the operands stack.
b. An opening bracket “ ( “, then push it into the operator stack.
c. A closing bracket “ )”, then- While the top of the operator stack is not equal to the opening bracket “ (”
- Pop an operator from the operator stack.
- Pop an operand B from the operand stack. Again, pop an operand A from the operand stack.
- Now, perform A operation B and push the result into the operand stack.
- Pop the opening bracket and discard the current closing bracket as well i.e. don’t add it to the operator stack.
d. An operator (+,-,*,/), then
-
While the size of the operator stack is greater than 0 and the operator on the top of the operator stack has precedence greater than or equal to the current character
-
Pop an operator from the operator stack.
-
Pop operand B from the operand stack. Pop again from the operand stack which gives operator A.
-
Perform A operation B.
-
Push the result into the operand stack
-
Push your current character i.e. the operator into the operator stack.
- While the top of the operator stack is not equal to the opening bracket “ (”
-
While the operator stack is not empty
a. Pop an operator from the operator stack.
b. Pop operand B from the operand stack. Pop again from the operand stack which gives operator A.
c. Perform A operation B.
d. Push the result into the operand stack. -
Now, when the operator stack is empty, you have the result at the top of the operand stack. Return that result.
So, this is the algorithm that we need to follow. Please read the algorithm at least twice so that you get familiar with the steps before going into the dry run.
Let us now have a dry run with an expression.
Dry Run
Have a look at the expression shown below.
We have 2 empty stacks ready with us. For simplicity, we have taken only 1 digit numbers right now. However, in the question, we can get more than a 1 digit number.
So, let us start with the first character. Since it is a number, we push it into the operand stack.
The next character is an operator. Since the operator stack is empty and we don’t have anything to compare this operator to, we will push it into the operator stack.
Next, we push operand 2 into the operand stack.
Next, we have the multiply operator. Since the precedence of the multiply operator is greater than that of the plus operator, this means that multiply should be at the top of the stack so that it gets evaluated first while popping the stack. Hence, we push it into the stack.
Now, we have an opening bracket. We simply push it into the operator stack.
Next, 3 gets pushed into the operand stack.
Next, we have a minus operator. Since we have an opening bracket at the top of the stack, the precedence of an operator can not be compared to an opening bracket. So, having an opening bracket at the top of the stack, in this case, is like the case of an empty operator stack. So, simply push minus into the stack.
Next, push 4 into the operand stack.
Now, we have a plus operator. The top of the stack is a minus operator. So, the precedence of both the operators is the same. Since it is same, the associativity rule says that minus should be evaluated first as it was on the left of the expression. Hence, we first pop out minus and pop 2 operands from the operand stack. The first operand becomes B and the second becomes A.
Perform A operation B and put it into the operand stack.
We again check the top operator of the stack and if it would have had a greater or equal priority than the current operator, we would have performed the operation again. However, we have the opening bracket at the top of the stack. So, just push plus into the stack.
Next, push 2 into the stack.
Now, since the precedence of the divide is greater, put it into the stack.
Push 3 into the operand stack.
Now, since we have a closing bracket, we have to perform operations until we get an opening bracket at the top of the stack.
Now, the situation looks like this.
So, try solving the remaining expression on the basis of the above rules.
So, now that we have understood the procedure, let us now write the code for the same.
#include <bits/stdc++.h>
using namespace std;
int precedence(char op){
if(op == '+'||op == '-')
return 1;
if(op == '*'||op == '/')
return 2;
return 0;
}
int operation(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 solve_infix_expression(string tokens){
int i;
stack <int> operands;
stack <char> operators;
for(i = 0; i < tokens.length(); i++){
//skip spaces
if(tokens[i] == ' ')
continue;
else if(tokens[i] == '('){
operators.push(tokens[i]);
}
else if(isdigit(tokens[i])){
int val = 0;
//converting string of characters to number
while(i < tokens.length() &&
isdigit(tokens[i]))
{
val = (val*10) + (tokens[i]-'0');
i++;
}
operands.push(val);
i--;
}
else if(tokens[i] == ')')
{
while(!operators.empty() && operators.top() != '(')
{
int val2 = operands.top();
operands.pop();
int val1 = operands.top();
operands.pop();
char op = operators.top();
operators.pop();
operands.push(operation(val1, val2, op));
}
if(!operators.empty())
operators.pop();
}
else
{
while(!operators.empty() && precedence(operators.top())
>= precedence(tokens[i])){
int val2 = operands.top();
operands.pop();
int val1 = operands.top();
operands.pop();
char op = operators.top();
operators.pop();
operands.push(operation(val1, val2, op));
}
operators.push(tokens[i]);
}
}
while(!operators.empty()){
int val2 = operands.top();
operands.pop();
int val1 = operands.top();
operands.pop();
char op = operators.top();
operators.pop();
operands.push(operation(val1, val2, op));
}
return operands.top();
}
int main() {
cout << solve_infix_expression("5 + 2 * (3 - 4 + 2 / 3) * 4 + 2");
return 0;
}
import java.util.*;
public class Main
{
public static int precedence(char op) {
if(op == '*' || op == '/') return 2;
else if(op == '+' || op == '-') return 1;
return 0;
}
public static int operation(int a, char op, int b) {
if(op == '+') {
return a+b;
} else if(op == '-') {
return a-b;
} else if(op == '*') {
return a*b;
}
return a/b;
}
public static int calculate(String s) {
Stack operators = new Stack<>();
Stack operands = new Stack<>();
for(int i=0;i= '0' && ch<='9') {
int num = 0;
while(i < s.length() && s.charAt(i) >='0' && s.charAt(i) <= '9') {
num = num * 10 + (s.charAt(i) -'0');
i++;
}
operands.push(num);
i--;
} else if(ch == ' ') {
} else if(ch == '(') {
operators.push(ch);
} else if(ch == ')') {
while(operators.size() > 0 && operators.peek() != '(') {
int B = operands.pop();
int A = operands.pop();
char op = operators.pop();
int res = operation(A,op,B);
operands.push(res);
}
operators.pop();
} else {
if(operators.size() == 0) {
operators.push(ch);
continue;
}
if(precedence(ch) > precedence(operators.peek())) {
operators.push(ch);
} else {
while(operators.size() > 0 && precedence(ch) <= precedence(operators.peek())) {
int B = operands.pop();
int A = operands.pop();
char op = operators.pop();
int res = operation(A,op,B);
operands.push(res);
}
operators.push(ch);
}
}
}
while(operators.size() > 0) {
int B = operands.pop();
int A = operands.pop();
char op = operators.pop();
int res = operation(A,op,B);
operands.push(res);
}
return operands.peek();
}
public static void main(String[] args)
{
String expression = "5 + 2 * (3 - 4 + 2 / 3) * 4 + 2";
System.out.println(calculate(expression));
}
}
Time Complexity: The time complexity of this solution is O(N) as any operand or operator enters just one time into the stack and get popped as we traverse the expression of length N.
Space Complexity: O(N) for the operands and the operators stack.
So, this is how we can evaluate an expression. Hope you liked the discussion. With this, we have completed this problem.
This article tried to discuss how to evaluate a string that represents mathematical expression. Hope this blog helps you understand and solve the problem. To practice more problems you can check out MYCODE | Competitive Programming at Prepbytes.