@@ -0,0 +1,2373 @@
+package com.freetymekiyan.algorithms.level.medium;%0A%0A/**%0A * Implement a basic calculator to evaluate a simple expression string.%0A * %3Cp%3E%0A * The expression string contains only non-negative integers, +, -, *, / operators and empty spaces . The integer%0A * division should truncate toward zero.%0A * %3Cp%3E%0A * You may assume that the given expression is always valid.%0A * %3Cp%3E%0A * Some examples:%0A * %223+2*2%22 = 7%0A * %22 3/2 %22 = 1%0A * %22 3+5 / 2 %22 = 5%0A * Note: Do not use the eval built-in library function.%0A * %3Cp%3E%0A * Tags: String%0A * Similar Problems: (H) Basic Calculator, (H) Expression Add Operators%0A */%0Apublic class BasicCalculator2 %7B%0A%0A    /**%0A     * The easy way would be using a stack to store high priority results and integers.%0A     * Then go through the stack to get final result.%0A     * How to remove the stack? How to do it in only one-pass?%0A     * We have only two priority levels, '*' '/' and '+' '-'.%0A     * They can separated into two results, high level value and low level value.%0A     * https://discuss.leetcode.com/topic/42684/explanation-for-java-o-n-time-o-1-space-solution%0A     */%0A    public int calculate(String s) %7B%0A        int lowVal = 0; // Result for low level operators like '+' and '-'%0A        int highVal = 0; // Result for high level operators like '*' and '/'%0A        int sign = 1; // 1 means '+', -1 means '-'%0A        int priority = 0; // 0 means '+' and '-', 1 means '*', -1 means '/'%0A        int num = 0; // Current number%0A%0A        for (int i = 0; i %3C s.length(); i++) %7B%0A            char c = s.charAt(i);%0A            if (Character.isDigit(c)) %7B%0A                num = num * 10 + (c - '0');%0A                if (i == s.length() - 1 %7C%7C !Character.isDigit(s.charAt(i + 1))) %7B%0A                    highVal = (priority == 0 ? num : (priority == 1 ? highVal * num : highVal / num));%0A                %7D%0A            %7D else if (c == '*' %7C%7C c == '/') %7B // Enter high level%0A                priority = (c == '*' ? 1 : -1); // Update priority%0A                num = 0; // Reset current number%0A            %7D else if (c == '+' %7C%7C c == '-') %7B // Enter low level%0A                lowVal += sign * highVal; // Accumulate high level result to low level%0A                sign = (c == '+' ? 1 : -1); // Update sign%0A                priority = 0; // Update priority%0A                num = 0; // Reset current number%0A            %7D%0A        %7D%0A%0A        return lowVal + sign * highVal;%0A    %7D%0A%0A%7D%0A

add Basic Calculator 2