Basic Calculator II | Leetcode 227

Показать описание

NADOS also enables doubt support, career opportunities and contests besides free of charge content for learning. 227. Basic Calculator II

Question Statement:
1. Given a string s which represents an expression, evaluate this expression and return its value.
2. while dividing (/) numbers discard the decimal part.Example 3/2 should be 1 insteed of 1.5

String consists of digits and operators ('+', '-', '*', '/') separated by some number of spaces.

Topic: #BasicCalculatorII #Leetcode227

Used #DataStructure: #Stack

#TimeComplexity: O(n)

#SpaceComplexity: O(n)

--------------------------------------------------------------

Linked Questions:

--------------------------------------------------------------

Smimilar Questions:

---------------------------------------------------------------

----------------------------------------------------------------

#BasicCalculatorII #Leetcode227 #Diwakar

.
.
.
Happy Programming !!! Pep it up 😍🤩
.
.
.
#pepcoding #code #coder #codinglife #programming #coding #java #freeresources #datastrucutres #pepcode #competitive #competitiveprogramming #softwareengineer #engineering #engineer

Рекомендации по теме

Комментарии

Possibly the best explanation of this algorithm on YouTube. Can't say the same about the implementation, playing too much with pointers is often bad for everyone.

bloody

I think if someone has done infix evaluation present in Stack and Queue Lvl 1, than it would be very easy to solve this problem
only small changes we have to do in the code when digit is appearing.
In case of lv1 one there were only single digit operands but here it is multiple digit operands.
rest Code is same
Code//
import java.util.*;
public class Main{
public static void main(String args[]){
Scanner sc = new Scanner(System.in);

String str = sc.nextLine();
Stack<Integer> operands = new Stack<>();
Stack<Character> operator = new Stack<>();

for(int i=0;i<str.length();i++){
char ch = str.charAt(i);

if(Character.isDigit(ch)){
int val = 0;
while(i<str.length() &&
val = val * 10 + (str.charAt(i)-'0');
i++;
}
i--;
operands.push(val);
}

else if(ch=='(') operator.push(ch);

else if(ch==')'){
while(operator.peek()!='('){
int v2 = operands.pop();
int v1 = operands.pop();
char sign = operator.pop();
int res = solve(v1, v2, sign);
operands.push(res);
}

operator.pop();
}

else
while(operator.size()>0 && operator.peek()!='(' &&
int v2 = operands.pop();
int v1 = operands.pop();
char sign = operator.pop();
int res = solve(v1, v2, sign);
operands.push(res);
}

operator.push(ch);
}
}

while(operator.size()>0){
int v2 = operands.pop();
int v1 = operands.pop();
char sign = operator.pop();
int res = solve(v1, v2, sign);
operands.push(res);
}

}

public static int precedence(char ch){
if(ch=='*'||ch=='/') return 2;
else return 1;
}

public static int solve(int v1, int v2, char ch){
if(ch=='+') return v1 + v2;
else if(ch=='-') return v1-v2;
else if(ch=='*') return v1 * v2;
else return v1/v2;
}
}

note: this solution will not work in previous problem becoz previous problem contains unary operator too which cant be handled by it.

ayushmansharma

For those having trouble in leetcode question, for CPP you have to first see the top element and then after calcuating the value pop it..
HERE IS THE CODE:
class Solution {
public:
int calculate(string s) {
stack<int> st;
int n = s.size();
char sign = '+';
for(int i=0;i<n;i++){
char ch = s[i];
if(isdigit(ch)){
int val = 0;
int pop, ans;
while(i<n && isdigit(s[i])){
val = val*10 + (s[i] - '0');
i++;
}
i--;
if(sign=='+'){
st.push(val);
}
else if(sign == '-'){
st.push(-val);
}
else if(sign == '*'){
pop = st.top();
ans = pop*val;
st.pop();
st.push(ans);
}
else if(sign == '/'){
pop = st.top();
ans = pop/val;
st.pop();
st.push(ans);
}
}
else if(ch!= ' '){
sign = ch;
}
}
int res = 0;
while(!st.empty()){
res += st.top();
st.pop();
}
return res;
}
};

piyushpandita