Basic Calculator ⭐⭐⭐

• 题目地址: https://leetcode-cn.com/problems/basic-calculator
• 执行时间: 0 ms
• 内存消耗: 2.4 MB
• 通过日期: 2019-09-08 19:00

题目内容

实现一个基本的计算器来计算一个简单的字符串表达式的值。

字符串表达式可以包含左括号 ( ，右括号 )，加号 + ，减号 -，非负整数和空格  。

示例 1:

输入: "1 + 1"
输出: 2

示例 2:

输入: " 2-1 + 2 "
输出: 3

示例 3:

输入: "(1+(4+5+2)-3)+(6+8)"
输出: 23

说明：

• 你可以假设所给定的表达式都是有效的。
• 请不要使用内置的库函数 eval。

解法

// Author: Netcan @ https://github.com/netcan/Leetcode-Rust
// Zhihu: https://www.zhihu.com/people/netcan

// Expr    ← Value (('+' / '-') Value)*
// Value   ← [0-9]+ / '(' Expr ')'
impl Solution {
    fn peek(ptr: &mut *const u8) -> char {
        unsafe { **ptr as char }
    }
    fn get(ptr: &mut *const u8) -> char {
        unsafe {
        let ch = Solution::peek(ptr);
        loop {
            *ptr = ptr.offset(1);
            if Solution::peek(ptr) != ' ' {
                break;
            }
        }
        ch
        }
    }

    // Value   ← [0-9]+ / '(' Expr ')'
    fn value(ptr: &mut *const u8) -> i32 {
        if Solution::peek(ptr) == '(' {
            Solution::get(ptr); // eat '('
            let val = Solution::expr(ptr);
            Solution::get(ptr); // eat ')'
            return val;
        }
        let mut val: i32 = 0;
        while Solution::peek(ptr) >= '0' && Solution::peek(ptr) <= '9' {
            val = val * 10 + (Solution::get(ptr) as u8 - '0' as u8) as i32;
        }
        val
    }

    // Expr    ← Value (('+' / '-') Value)*
    fn expr(ptr: &mut *const u8) -> i32 {
        let mut lhs = Solution::value(ptr);
        loop {
            let op = Solution::peek(ptr);
            match op {
                '+' => {
                    Solution::get(ptr); // eat op
                    lhs += Solution::value(ptr);
                },
                '-' => {
                    Solution::get(ptr); // eat op
                    lhs -= Solution::value(ptr);
                }
                _ => { break; }
            }
        }
        lhs
    }

    pub fn calculate(mut expr: String) -> i32 {
        expr = expr.trim().to_string();
        expr.push(0 as char); // add '\0' to string end
        Solution::expr(&mut expr.as_ptr())
    }
}