Solution For Basic Calculator Iii
Problem Statement:
Implement a basic calculator to evaluate a simple expression string.
The expression string contains only non-negative integers, +, -, *, / operators , open ( and closing parentheses ( ). The integer division should truncate toward zero.
You may assume that the given expression is always valid. All intermediate results will be in the range of [-231, 231 – 1].
Example 1:
Input: expression = “1+1”
Output: 2
Example 2:
Input: expression = “6-4/2”
Output: 4
Example 3:
Input: expression = “2(5+52)/3+(6/2+8)”
Output: 21
Example 4:
Input: expression = “(2+6 3+5- (314/7+2)*5)+3″
Output: -12
Approach:
In order to solve this problem, first, we need to identify the different operators and their priorities. There are two types of operators, Unary and Binary operators.
Unary Operators include + and – for positive and negative values, respectively. It can act as a prefix or postfix operator for a number.
Binary Operators include +, -, *, and / along with brackets () to indicate precedence.
We can use a stack to keep track of the result so far. We push the sign of the next number we encounter on the stack, and then we push the number itself onto the stack.
When we encounter a closing bracket, we pop the stack until we encounter the corresponding opening bracket. Then we evaluate the expression on the stack and push the result onto the stack again.
We can then evaluate the entire expression on the stack and return the final result.
Let’s implement the solution step-by-step:
Step 1: Initialize a stack to keep track of the result so far.
Step 2: Initialize variables to keep track of the current value, the sign of the current value, and the result.
Step 3: Loop through all the characters in the expression.
Step 4: If the current character is a digit, we add it to the current value.
Step 5: If the current character is an operator or the last character, we perform the appropriate operation based on the previous operator.
Step 6: If the current character is an opening bracket, we push the current value and the sign onto the stack and set the current value and sign to 0 and +, respectively.
Step 7: If the current character is a closing bracket, we evaluate the expression on the stack and push the result onto the stack again.
Step 8: After the loop, we evaluate the entire expression on the stack and return the final result.
Solution:
class Solution {
public:
int calculate(string s) {
stack
int res = 0;
int cur = 0;
int sign = 1;
int n = s.size();
for(int i=0; i<n; i++){
char c = s[i];
if(isdigit(c)){
cur = cur10+(c-‘0′);
}
else if(c==’+’ || c==’-‘ || c==’‘ || c==’/’ || i==n-1){
if(c==’+’ || c==’-‘){
res += signcur;
cur = 0;
sign = (c==’+’) ? 1 : -1;
}
else if(c==’‘ || c==’/’){
int a = cur;
i++;
while(s[i]==’ ‘) i++;
char d = s[i];
i++;
while(s[i]==’ ‘) i++;
int b = 0;
while(i<n && isdigit(s[i])){
b = b10+(s[i]-‘0′);
i++;
}
i–;
if(d==’‘){
cur = ab;
}
else{
cur = a/b;
}
}
else{
res += signcur;
cur = 0;
if(st.top()==-1){
st.pop();
sign = -1;
}
else{
sign=1;
}
int val = st.top();
st.pop();
res = val + signres;
}
}
else if(c =='(‘){
st.push(res);
if(sign==-1){
st.push(-1);
sign = 1;
}
st.push(sign);
res = 0;
cur =0;
sign = 1;
}
else if(c==’)’){
res += signcur;
cur = 0;
if(st.top()==-1){
st.pop();
sign = -1;
}
else{
sign = 1;
}
int val = st.top();
st.pop();
res = val + sign*res;
}
}
return res;
}
};
Time Complexity: O(n), where n is the length of the expression.
Space Complexity: O(n), we use a stack to keep track of intermediate results.
Step by Step Implementation For Basic Calculator Iii
/**
* Implement a basic calculator to evaluate a simple expression string.
*
* The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces .
*
* The expression string contains only non-negative integers, +, -, *, / operators , open ( and closing parentheses ) and empty spaces . The integer division should truncate toward zero.
*
* You may assume that the given expression is always valid. All intermediate results will be in the range of [-2147483648, 2147483647].
*
* Some examples:
*
* "1 + 1" = 2
* " 6-4 / 2 " = 4
* "2*(5+5*2)/3+(6/2+8)" = 21
* "(2+6* 3+5- (3*14/7+2)*5)+3"=-12
*/
class Solution {
public int calculate(String s) {
Stack stack = new Stack<>();
int operand = 0;
int result = 0; // For the on-going result
int sign = 1; // 1 means positive, -1 means negative
for (int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
if (Character.isDigit(ch)) {
// Forming operand, since it could be more than one digit
operand = 10 * operand + ch - '0';
} else if (ch == '+') {
// Evaluate the expression to the left,
// with result, sign, operand
result += sign * operand;
// Save the recently encountered '+' sign
sign = 1;
// Reset operand
operand = 0;
} else if (ch == '-') {
result += sign * operand;
sign = -1;
operand = 0;
} else if (ch == '(') {
// Push the result and sign on to the stack, for later
// We push the result first, then sign
stack.push(result);
stack.push(sign);
// Reset operand and result, as if new evaluation begins for the new sub-expression
sign = 1;
result = 0;
} else if (ch == ')') {
// Evaluate the expression to the left
// with result, sign and operand
result += sign * operand;
// ')' marks end of expression within a set of parenthesis
// Its result is multiplied with sign on top of stack
// as stack.pop() is the sign before the parenthesis
result *= stack.pop();
// Then add to the next operand on the top.
// as stack.pop() is the result calculated before this parenthesis
// (operand on stack) + (sign on stack * (result from parenthesis))
result += stack.pop();
// Reset the operand
operand = 0;
}
}
return result + (sign * operand);
}
} class Solution:
def calculate(self, s: str) -> int:
# This is a comment
# Your code here
return 0/**
* @param {string} s
* @return {number}
*/
var calculate = function(s) {
};class Solution {
public:
int calculate(string s) {
stack nums, ops;
int num = 0;
int rst = 0;
int sign = 1;
for (char c : s) {
if (isdigit(c)) {
num = num * 10 + c - '0';
}
else {
rst += sign * num;
num = 0;
if (c == '+') sign = 1;
if (c == '-') sign = -1;
if (c == '(') {
nums.push(rst);
ops.push(sign);
rst = 0;
sign = 1;
}
if (c == ')' && ops.size()) {
rst = ops.top() * rst + nums.top();
ops.pop(); nums.pop();
}
}
}
rst += sign * num;
return rst;
}
}; using System;
using System.Collections.Generic;
public class Solution {
public int Calculate(string s) {
//Create a stack to store the operands (numbers)
Stack stack = new Stack();
//Create a variable to store the current operand
int currNum = 0;
//Create a variable to store the current operation
char currOp = '+';
//Loop through the input string
for (int i = 0; i < s.Length; i++) {
//If the current character is a digit
if (Char.IsDigit(s[i])) {
//Update the current operand
currNum = currNum * 10 + (s[i] - '0');
}
//If the current character is not a space
if (s[i] != ' ') {
//If the current character is an operator
if (s[i] == '+' || s[i] == '-' || s[i] == '*' || s[i] == '/') {
//Evaluate the expression to the left of the operator
//based on the current operator
switch (currOp) {
case '+':
stack.Push(currNum);
break;
case '-':
stack.Push(-currNum);
break;
case '*':
stack.Push(stack.Pop() * currNum);
break;
case '/':
stack.Push(stack.Pop() / currNum);
break;
}
//Update the current operator
currOp = s[i];
//Reset the current operand
currNum = 0;
}
}
}
//Evaluate the expression to the right of the last operator
switch (currOp) {
case '+':
stack.Push(currNum);
break;
case '-':
stack.Push(-currNum);
break;
case '*':
stack.Push(stack.Pop() * currNum);
break;
case '/':
stack.Push(stack.Pop() / currNum);
break;
}
//Return the result
return stack.Sum();
}
}