Basic Calculator Ii

                                            
class Solution {
public:
    int calculate(string s) {
        int num = 0;
        char sign = '+';
        stack<int> st;
        for (int i = 0; i < s.length(); i++) {
            if (isdigit(s[i])) {
                num = num * 10 + (s[i] - '0');
            }
            if ((!isdigit(s[i]) && s[i] != ' ') || i == s.length() - 1) {
                if (sign == '+') {
                    st.push(num);
                } else if (sign == '-') {
                    st.push(-num);
                } else if (sign == '*') {
                    int prev = st.top();
                    st.pop();
                    st.push(prev * num);
                } else if (sign == '/') {
                    int prev = st.top();
                    st.pop();
                    st.push(prev / num);
                }
                sign = s[i];
                num = 0;
            }
        }
        int total = 0;
        while (!st.empty()) {
            total += st.top();
            st.pop();
        }
        return total;
    }
};

                                            
class Solution {
    public int calculate(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        
        Stack<Integer> stack = new Stack<>();
        int num = 0;
        char sign = '+';
        
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (Character.isDigit(c)) {
                num = num * 10 + (c - '0');
            }
            if ((!Character.isDigit(c) && c != ' ') || i == s.length() - 1) {
                if (sign == '+') {
                    stack.push(num);
                } else if (sign == '-') {
                    stack.push(-num);
                } else if (sign == '*') {
                    stack.push(stack.pop() * num);
                } else if (sign == '/') {
                    stack.push(stack.pop() / num);
                }
                sign = c;
                num = 0;
            }
        }
        
        int result = 0;
        for (int numToAdd : stack) {
            result += numToAdd;
        }
        
        return result;
    }
}

                                            
class Solution(object):
    def calculate(self, s):
        stack = []
        num = 0
        sign = "+"
        for i in range(len(s)):
            if s[i].isdigit():
                num = num * 10 + int(s[i])
            if (not s[i].isdigit() and s[i] != " ") or i == len(s) - 1:
                if sign == "+":
                    stack.append(num)
                elif sign == "-":
                    stack.append(-num)
                elif sign == "*":
                    stack.append(stack.pop() * num)
                elif sign == "/":
                    top = stack.pop()
                    if top < 0:
                        stack.append(-(-top//num))
                    else:
                        stack.append(top // num)
                sign = s[i]
                num = 0
        return sum(stack)

                                            
public class Solution {
    public int Calculate(string s) {
        int result = 0;
        int num = 0;
        char sign = '+';
        Stack<int> stack = new Stack<int>();

        for (int i = 0; i < s.Length; i++) {
            if (char.IsDigit(s[i])) {
                num = num * 10 + (s[i] - '0');
            }
            if ((!char.IsDigit(s[i]) && ' ' != s[i]) || i == s.Length - 1) {
                if (sign == '+') {
                    stack.Push(num);
                } else if (sign == '-') {
                    stack.Push(-num);
                } else if (sign == '*') {
                    stack.Push(stack.Pop() * num);
                } else if (sign == '/') {
                    stack.Push(stack.Pop() / num);
                }
                sign = s[i];
                num = 0;
            }
        }

        foreach (int item in stack) {
            result += item;
        }

        return result;
    }
}

                                            
function calculate(s: string): number {
    const stack: number[] = [];
    let num = 0;
    let sign = '+';

    for (let i = 0; i < s.length; i++) {
        const char = s[i];

        if (!isNaN(Number(char)) && char !== ' ') {
            num = num * 10 + Number(char);
        }

        if (isNaN(Number(char)) || i === s.length - 1) {
            if (sign === '+') {
                stack.push(num);
            } else if (sign === '-') {
                stack.push(-num);
            } else if (sign === '*') {
                stack.push(stack.pop() * num);
            } else if (sign === '/') {
                stack.push(Math.trunc(stack.pop() / num));
            }

            sign = char;
            num = 0;
        }
    }

    return stack.reduce((acc, curr) => acc + curr, 0);
};

                                            
class Solution {
    /**
     * @param String $s
     * @return Integer
     */
    function calculate($s) {
        $len = strlen($s);
        $stack = [];
        $num = 0;
        $sign = '+';
        for ($i = 0; $i < $len; $i++) {
            if (is_numeric($s[$i])) {
                $num = $num * 10 + intval($s[$i]);
            }
            if ((!is_numeric($s[$i]) && $s[$i] !== ' ') || $i === $len - 1) {
                if ($sign === '+') {
                    array_push($stack, $num);
                } elseif ($sign === '-') {
                    array_push($stack, -$num);
                } elseif ($sign === '*') {
                    $stack[count($stack) - 1] *= $num;
                } elseif ($sign === '/') {
                    $stack[count($stack) - 1] = intdiv($stack[count($stack) - 1], $num);
                }
                $sign = $s[$i];
                $num = 0;
            }
        }
        return array_sum($stack);
    }
}

                                            
class Solution {
    func calculate(_ s: String) -> Int {
        var stack = [Int]()
        var num = 0
        var sign = "+"
        
        for (index, char) in s.enumerated() {
            if let digit = char.wholeNumberValue {
                num = num * 10 + digit
            }
            
            if !char.isNumber && char != " " || index == s.count - 1 {
                switch sign {
                    case "+":
                        stack.append(num)
                    case "-":
                        stack.append(-num)
                    case "*":
                        stack.append(stack.removeLast() * num)
                    case "/":
                        stack.append(stack.removeLast() / num)
                    default:
                        break
                }
                
                sign = String(char)
                num = 0
            }
        }
        
        return stack.reduce(0, +)
    }
}

                                            
class Solution {
    fun calculate(s: String): Int {
        if(s.isEmpty()) return 0
        
        var num = 0
        var stack = mutableListOf<Int>()
        var sign = '+'
        
        for(i in s.indices) {
            if(s[i].isDigit()) {
                num = num * 10 + (s[i] - '0')
            }
            if((!s[i].isDigit() && s[i] != ' ') || i == s.length - 1) {
                when(sign) {
                    '+' -> stack.add(num)
                    '-' -> stack.add(-num)
                    '*' -> stack[stack.size-1] = stack[stack.size-1] * num
                    '/' -> stack[stack.size-1] = stack[stack.size-1] / num
                }
                sign = s[i]
                num = 0
            }
        }
        
        return stack.sum()
    }
}

                                            
# @param {String} s
# @return {Integer}
def calculate(s)
    stack = []
    num = 0
    sign = '+'
    s.chars.each_with_index do |char, i|
        num = num * 10 + char.to_i if char.match?(/\d/)
        if ('+-*/'.include?(char) || i == s.length - 1)
            case sign
            when '+'
                stack.push(num)
            when '-'
                stack.push(-num)
            when '*'
                stack.push(stack.pop * num)
            when '/'
                pop_num = stack.pop
                if pop_num.negative?
                    stack.push(-((-pop_num) / num))
                else
                    stack.push(pop_num / num)
                end
            end
            num = 0
            sign = char
        end
    end
    stack.sum
end

                                            
object Solution {
    def calculate(s: String): Int = {
        var stack = List.empty[Int]
        var num = 0
        var sign = '+'
        
        for (i <- 0 until s.length) {
            val c = s(i)
            
            if (Character.isDigit(c)) {
                num = num * 10 + (c - '0')
            }
            
            if ((!Character.isDigit(c) && c != ' ') || i == s.length - 1) {
                sign match {
                    case '+' => stack = num :: stack
                    case '-' => stack = -num :: stack
                    case '*' => stack = stack.head * num :: stack.tail
                    case '/' => stack = stack.head / num :: stack.tail
                }
                
                num = 0
                sign = c
            }
        }
        
        stack.sum
    }
}

                                            
impl Solution {
    pub fn calculate(s: String) -> i32 {
        let mut stack = Vec::new();
        let chars: Vec<char> = s.chars().filter(|c| *c != ' ').collect();
        let mut num = 0;
        let mut sign = '+';

        for (i, &c) in chars.iter().enumerate() {
            if c.is_digit(10) {
                num = num * 10 + c.to_digit(10).unwrap() as i32;
            }
            if !c.is_digit(10) || i == chars.len() - 1 {
                match sign {
                    '+' => stack.push(num),
                    '-' => stack.push(-num),
                    '*' => {
                        let prev = stack.pop().unwrap();
                        stack.push(prev * num);
                    }
                    '/' => {
                        let prev = stack.pop().unwrap();
                        stack.push(prev / num);
                    }
                    _ => {}
                }
                sign = c;
                num = 0;
            }
        }

        stack.iter().sum()
    }
}

To solve this coding challenge, let's break down the problem and understand the requirements and constraints. We need to evaluate a given mathematical expression represented by a string. The expression consists of non-negative integers and the operators '+', '-', '*', '/'. The order of operations should adhere to standard mathematical rules: multiplication and division should be performed before addition and subtraction. Additionally, we should handle spaces in the string and ensure that integer division truncates towards zero.

Explanation

This problem can be solved through an algorithm that parses the expression character by character and evaluates it using a stack-based approach. The stack will help manage the order of operations due to its Last-In-First-Out (LIFO) nature. We will use the following steps:

Initialize a stack to keep track of numbers and intermediate results.
Iterate through each character in the string while keeping track of the current number being processed and the last seen operator.
Process the characters :

If the character is a digit, we update the current number.
If the character is an operator or the end of the string is reached, perform the operation indicated by the last seen operator on the current number and update the stack accordingly.
After processing the operator, reset the current number and update the last seen operator.

Sum the stack at the end to obtain the final result.

Detailed Steps in Pseudocode

Step 1: Initialize Variables

stack

to store intermediate results.
current_number

to build multi-digit numbers.
last_operator

initially set to '+' since the first number is either positive or added.

Step 2: Iterate Through Characters in String

For each character
char

in the string
expression

:

If
char

is a digit, update
current_number

by appending the digit.
If
char

is an operator or the end of the string:

Apply
last_operator

on
current_number

:

If
last_operator

is '+', push
current_number

onto
stack

.
If
last_operator

is '-', push
-current_number

onto
stack

.
If
last_operator

is '*', multiply the top of the stack with
current_number

and push the result back.
If
last_operator

is '/', perform integer division of the top of the stack by
current_number

(handle truncation toward zero).

Reset
current_number

and update
last_operator

to
char

.

Step 3: Sum the Stack

Sum all values in the stack to obtain the final result.

Pseudocode

                                            
# Initialize stack to store intermediate results
stack = []

# Initialize current_number to build multi-digit numbers
current_number = 0

# Initialize last_operator to '+'
last_operator = '+'

# Iterate over each character in the string 'expression'
for each char in expression:
    # If char is a digit, build the current number
    if char is digit:
        current_number = current_number * 10 + integer_value_of(char)

    # If char is an operator or end of string is reached
    if char is operator or end of string:
        # Process based on the last seen operator
        if last_operator is '+':
            push current_number onto stack
        if last_operator is '-':
            push -current_number onto stack
        if last_operator is '*':
            top_number = pop from stack
            push (top_number * current_number) onto stack
        if last_operator is '/':
            top_number = pop from stack
            push (integer_divide top_number by current_number with truncation) onto stack
        
        # Reset current_number
        current_number = 0

        # Update last_operator
        last_operator = char

# Sum all values in the stack to get the final result
result = sum all values in stack

This thorough explanation and the pseudocode provided should assist in tackling the given coding challenge efficiently. The key is maintaining the stack for intermediate results and managing the precedence of operations correctly.