Fun With Expressions Problem | Evaluating the Mathematical Expressions
Table of contents
Problem Statement
Given a string s which represent an expression, evaluate this expression.(No brackets involved)
Integer division should truncate towards zero.
Example 1:
Input: s = "10*20+10"
Output: 210
Example 2:
Input: s = "16*5-5/15"
Output: 80
You are given a string that contains mathematical numbers and operators('+', '-', '*', '/'). And we need to evaluate the expression and return the answer. The input string may contains "Spaces"
Ex: String expression = "10*20+10"
Output : 210
Explanation : According to BODMAS(Bracket of Division Multiplication Addition Subtraction),
(10*20)+10=200+10
\=210
We can solve this by doing addition like : X*Y+A-B ==> (X*Y)+(A)+(-B)
Approach I ( By using Stack) :
Initialize number =0; current_character='+'
Initialize a stack of Integer values
Traverse or iterate through each and every character of the given input string.
Check if the character is "digit"
If the character is digit , then check or iterate until the complete number is generated
Example : String s = "100*2+10", here while traversing through each character, At index=0, we get '1' and at index=1, we get '0' and at index=2 we get '0'. We need to combine all the characters so that it can form a number.
To do this, we can do the following : number = (number*10)+(current_character-'0')
Example : String s="100+1" :
1st iteration : current_character is '1' (which is a digit)
so, number = (number*10)+(ch-'0') ==> number = (0*10)+('1'-'0') ==> number=0+(92-91) [based on ASCII] ==> number=0+1 ==> number=1
2nd iteration : current_character is '0' (which is a digit)
so, number = (number*10)+(ch-'0') ==> number = (1*10)+('0'-'0') ==> number=10+(92-91) [based on ASCII] ==> number=10+0 ==> number=10
3rd iteration : current_character is '0' (which is a digit)
so, number = (number*10)+(ch-'0') ==> number = (10*10)+('0'-'0') ==> number=100+(92-91) [based on ASCII] ==> number=100+0 ==> number=100. So finally we got the complete integer.
Next if the character is not a digit or the i=s.length()-1 [because last charcater will always end with digit and in this case this should enter the condition], then
Case 1 : operator is '+', then push into the stack
Case 2 : operator is '-', then push into the stack with the sign '-' [since, X*Y+A-B ==> (X*Y)+(A)+(-B) ]
Case 3 : operator is '*', then multiply with the number that is present in the top of the stack and push into the stack and also pop out the number that was there before performing multiplication.
Case 4 : operator is '/', then divide with the number that is present in the top of the stack and push into the stack and also pop out the number that was there before performing division.
After these cases being checked, update the operator to current_character and make number to '0' because next new number will come in the same fashion.
After completion of the whole loop. Add all the elements in the stack.
Note : This works only if the input string doesn't contains any brackets
Java
import java.util.Scanner;
import java.util.Stack;
class Solution
{
public static int Evaluate_Expression(String s)
{
Stack<Integer> ans = new Stack<>();
int number = 0;
char operator = '+';
for( int i=0; i<s.length(); i++){
char current_character = s.charAt(i);
if( Character.isDigit(current_character) )
number = (number*10) + current_character-'0';
if( (!Character.isDigit(current_character) && current_character!=' ') || i==s.length()-1 ){
if( operator == '+') ans.push(number);
else if( operator == '-') ans.push(-1*number);
else if( operator == '*') ans.push( number*ans.pop());
else if( operator == '/') ans .push( ans.pop()/number);
number =0;
operator = current_character;
}
}
int result = 0;
while(!ans.isEmpty()){
result = result + ans.pop();
}
return result;
}
public static void main(String args[]){
Scanner scanner = new Scanner(System.in);
//Read string input from the user
String userInput = scanner.next();
int expression_answer = Evaluate_Expression(userInput);
System.out.print(expression_answer);
}
}
output :
Input: s = "10\20+10"*
Output: 210
Example 2:
Input: s = "16\5-5/15"*
Output: 80
Time Complexity : O(s,length())
Space Complexity : O(N)