224. Basic Calculator

[jason89521]

Practice Dates

• 2024/05/14

Description

Link: https://leetcode.com/problems/basic-calculator/description/

Solution

Create three variables to record the current sign, number, and the result, and create a stack to record the temporary result (when encountering a left parenthesis). Next, iterate through the string. When encountering a digit character, multiply the number by 10 and add the digit. Continue until encountering a '+' or a '-', then add the result by sign * number and reset the number to zero, resetting the sign to 1 or -1 based on the character encountered ('+' or '-').

When encountering a left parenthesis, push the current result and the sign onto the stack, and reset the number, result, and sign. When encountering a right parenthesis, first sum up the number as when encountering a '+' or a '-'. Then pop the top of the stack, which records the previous result and the previous sign. Set result to prev_result + prev_sign * result.

impl Solution {
    pub fn calculate(s: String) -> i32 {
        let mut stack = vec![];
        let mut sign = 1;
        let mut number = 0;
        let mut result = 0;
        for ch in s.chars() {
            match ch {
                '(' => {
                    stack.push((sign, result));
                    result = 0;
                    sign = 1;
                    number = 0;
                }
                ')' => {
                    result += sign * number;
                    number = 0;
                    let (prev_sign, prev_result) = stack.pop().unwrap();
                    result = prev_result + prev_sign * result;
                }
                ' ' => {

                }
                '+' => {
                    result += sign * number;
                    number = 0;
                    sign = 1;
                }
                '-' => {
                    result += sign * number;
                    number = 0;
                    sign = -1;
                }
                _ => {
                    number *= 10;
                    number += (ch as i32) - ('0' as i32);
                }
            }
        }

        result + sign * number
    }
}

Performance

Time complexity: