227. Basic Calculator II

littlelightss 发布于2019-08-14 18:01 / 807人阅读

摘要：但是乘除就会有问题，要特殊处理。这题只有加减和括号，优先级就是括号里的先计算，所有我们把括号里的内容当做操作的基本单位。遇到遇到和，遇到遇到，弹出再遇到弹出，这里只是把对数字的操作变成了对的操作，去括号的逻辑一样。

The expression string contains only non-negative integers, +, -, *, / operators and empty spaces. 
The integer division should truncate toward zero.

"3+2*2" = 7
" 3/2 " = 1
" 3+5 / 2 " = 5

这题只有基本的四则运算符号，不包含括号。模拟计算器的难点在于，运算法则里符号有优先级，先乘除后加减。
人类的逻辑是先找到乘除的部分，多带带计算这些部分，变成整数，和加减一起运算，代码模拟起来麻烦且费时。
按照从左到右的顺序扫描，遇到加减直接运算，不会出错。但是乘除就会有问题，要特殊处理。
这里我们把上次遇到的数字存到stack里，如果遇到乘除符合，说明上次操作不对，需要从结果里减去这个数字。
而且还可以得到乘数和除数是多少，进行乘除部分的操作。

public class Solution {
    public int calculate(String s) {
        Stack stk = new Stack();
        int res = 0, num = 0;
        char lastSign = "+";
        char[] cArray = s.toCharArray();
        
        for(int i=0; i < cArray.length; i++){
            char c = cArray[i];
            if(c >= "0" && c <= "9"){
                num = num*10 + c -"0";
            }
            
            if(c == "+" || c == "-" || c == "*" || c == "/" || i == cArray.length-1){
                if(lastSign == "+" || lastSign == "-"){
                    int temp = lastSign == "+" ? num : -num;
                    stk.push(temp);
                    res += temp;
                }
                if(lastSign == "*" || lastSign == "/"){
                    res -= stk.peek();
                    int temp = lastSign == "*" ? stk.pop()*num : stk.pop()/num;
                    stk.push(temp);
                    res += temp;
                }
                lastSign = c;
                num = 0;
            }
        }
        return res;
    }
}

224 Basic Calculator

The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces.
"1 + 1" = 2
" 2-1 + 2 " = 3
"(1+(4+5+2)-3)+(6+8)" = 23

这题只有加减和括号，优先级就是括号里的先计算，所有我们把括号里的内容当做操作的基本单位。
括号外的符号就当做整体的符号，最后和括号外的同层数字进行加减运算。
比如 (2-(2+1))
初始化sign = 1, res =0;
stk{1,2,3,4,5} 简单表示stk最右的栈顶。
遇到(, stk{0, 1}, 遇到2和-， stk{0,1,2,-1}
遇到2+1 = 3, 遇到)， stk弹出res = 3*(-1) +2 = -1, stk{0,1}
再遇到), stk弹出，res = -1*1 + 0 = -1.

public class Solution {
    public int calculate(String s) {
        int sign = 1, result = 0;
        Stack stk = new Stack();
        char[] cArray = s.toCharArray();
        for(int i=0; i< cArray.length; i++){
            if(Character.isDigit(cArray[i])){
                int num = 0;
                while(i < cArray.length && Character.isDigit(cArray[i])){
                    num = 10*num + cArray[i] - "0";
                    i++;
                }
                i--;
                result = result + sign*num;
            } else if(cArray[i] == "+"){
                sign = 1;
            } else if(cArray[i] == "-"){
                sign = -1;
            } else if(cArray[i] == "("){
                stk.push(result);
                stk.push(sign);
                result = 0;
                sign = 1;
            } else if(cArray[i] == ")"){
                result = result*stk.pop() + stk.pop();
            }
        }
        return result;
    }
}

394 Decode String

The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times.
s = "3[a]2[bc]", return "aaabcbc".
s = "3[a2[c]]", return "accaccacc".
s = "2[abc]3[cd]ef", return "abcabccdcdcdef".

这里只是把对数字的操作变成了对str的操作，去括号的逻辑一样。

public class Solution {
    public String decodeString(String s) {
        Stack numStk = new Stack<>();
        Stack sbStk = new Stack<>();
        int num = 0;
        StringBuilder cur = new StringBuilder();
        for(char c: s.toCharArray()){
            if(c >= "0" && c <= "9"){
                num = num*10 + c -"0";
            } else if(c == "["){
                numStk.push(num);
                sbStk.push(cur);
                num = 0;
                cur = new StringBuilder();
            } else if(c == "]"){
                StringBuilder temp = cur;
                cur = sbStk.pop();
                for(int i = numStk.pop(); i > 0; i--) cur.append(temp);
            } else {
                cur.append(c);
            }
        }
        return cur.toString();
    }
}

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/66943.html

Leetcode[227] Basic Calculator II

摘要：复杂度思路用两个来分别记录当前的结果和操作符注意每一次统计当前的的时候，要看一下下一位的操作符。有一种的方法，是表示的是匹配任意的空白符，包括空格，制表符，换行符，中文全角空格等。也可以用更简单的方法，。 LeetCode[227] Basic Calculator II Implement a basic calculator to evaluate a simple expres...

chaos_G 2019-08-14 16:55 评论0 收藏0
[LeetCode] 227. Basic Calculator II

Problem Implement a basic calculator to evaluate a simple expression string. The expression string contains only non-negative integers, +, -, *, / operators and empty spaces . The integer division sho...

silvertheo 2019-08-19 11:11 评论0 收藏0
224. Basic Calculator & 227. Basic Calculator

摘要：题目链接，就是感觉条件有点多简单点的写法，把直接用存在里面，就存成，存成题目链接这题就是碰到在加减后面怎么处理的问题。用一个来表示之前的，所以碰到现在是乘的时候就，除类似。 224. Basic Calculator 题目链接：https://leetcode.com/problems... stack，就是感觉条件有点多 public class Solution { pub...

_DangJin 2019-08-14 17:35 评论0 收藏0
[Leetcode] Basic Calculator 基本计算器

摘要：难点在于多了括号后如何处理正负号。但是每多一个括号，都要记录下这个括号所属的正负号，而每当一个括号结束，我们还要知道出来以后所在的括号所属的正负号。 Basic Calculator I 最新更新请见: https://yanjia.li/zh/2019/01/... Implement a basic calculator to evaluate a simple express...

ky0ncheng 2019-08-14 12:38 评论0 收藏0
Leetcode[224] Basic Calculator

摘要：复杂度思路将字符串先转换成后缀表达式，再将其出来。 Leetcode[224] Basic Calculator Implement a basic calculator to evaluate a simple expression string. The expression string may contain open ( and closing parentheses ),...

William_Sang 2019-08-14 16:55 评论0 收藏0