经典算法一：calculator

1.简单的加减问题，比如：1+2-3=0

1+2-3 可以看作 +1+2-3 ，那么我们可以逐个把这些数字放到stack，最后加起来

class Solution {
    public int calculate(String s) {
        Stack stack = new Stack();
        char op = '+';//开始遍历前默认是正数
        int num=0;
        for(int i=0;i){
            char c = s.charAt(i);
            if(Character.isDigit(c)){
                num=num*10+(c-'0');
            }
            if( i==s.length()-1 || c=='+' || c=='-' ){
                if(op=='+') stack.push(num);
                else stack.push(-num);
                num=0;
                op = c;
            }
        }
        int sum = 0;
        for(int n:stack) sum+=n;
        return sum;
    }
}

2.如果再加上乘除的问题，比如：1+2-3*4 = -9;

加了乘除后，乘除的优先级要高于加减，因此我们遇到*/的时候，我们先把前面的数组pop出来做完计算再压回stack

class Solution {
    public int calculate(String s) {
        Stack stack = new Stack();
        char op = '+';
        int num=0;
        for(int i=0;i){
            char c = s.charAt(i);
            if(Character.isDigit(c)){
                num=num*10+(c-'0');
            }
            if( i==s.length()-1 || c=='+' || c=='-' || c=='*' || c=='/' ){
                if(op=='*') stack.push(stack.pop()*num);
                else if(op=='/') stack.push(stack.pop()/num);
                else if(op=='+') stack.push(num);
                else stack.push(-num);
                num=0;
                op = c;
            }
        }
        int sum = 0;
        for(int n:stack) sum+=n;
        return sum;
    }
}

3.如果在+-*/基础上增加了括号，比如：5+(3+2-1)*4 = 21

class Solution {
    int i = 0;
    public int calculate(String s) {
        Stack stack = new Stack();
        char op = '+';
        int num=0;
        while(i<s.length()){
            char c = s.charAt(i++);
            if(c>='0'&&c<='9') num=num*10+(c-'0');
            if(c=='(') num = calculate(s);//如果遇到括号，我们把括号里的东西当成一个新的表达式，递归调用计算结果
            if( i==s.length() || c=='+' || c=='-' || c=='*' || c=='/' || c==')' ){//坑点：这里不能是else if，因为此处condition也包含上面的情况； 另外)的时候相当于 i==s.length() 已经到达当前表达式的结尾
                if(op=='*') stack.push(stack.pop()*num);
                else if(op=='/') stack.push(stack.pop()/num);
                else if(op=='+') stack.push(num);
                else stack.push(-num);
                num=0;
                op = c;
            }
            if(c==')') break;//坑点：这里别忘了')'的时候要结束当前表达式计算跳出循环
        }
        int sum = 0;
        for(int n:stack) sum+=n;
        return sum;
    }
}

227. Basic Calculator II Medium

Given a string s which represents an expression, evaluate this expression and return its value.

The integer division should truncate toward zero.

You may assume that the given expression is always valid. All intermediate results will be in the range of [-231, 231 - 1].

Note: You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as eval().

Example 1:

Input: s = "3+2*2"
Output: 7

Example 2:

Input: s = " 3/2 "
Output: 1

Example 3:

Input: s = " 3+5 / 2 "
Output: 5

Constraints:

1 <= s.length <= 3 * 105
s consists of integers and operators ('+', '-', '*', '/') separated by some number of spaces.
s represents a valid expression.
All the integers in the expression are non-negative integers in the range [0, 231 - 1].
The answer is guaranteed to fit in a 32-bit integer.

class Solution {
    public int calculate(String s) {
        Stack stack = new Stack();
        char op = '+';
        int num = 0;
        while(i<s.length()){
            char c = s.charAt(i++);
            if(c>='0' && c<='9') num=num*10+(c-'0');
            if(i==s.length() || c=='+' || c=='-' || c=='*' || c=='/' ){
                if(op=='+') stack.push(num);
                else if(op=='-') stack.push(-num);
                else if(op=='*') stack.push(stack.pop()*num);
                else if(op=='/') stack.push(stack.pop()/num);
                op = c;
                num=0;
            }
        }
        int sum = 0;
        for(int n:stack) sum+=n;
        return sum;
    }
    private int i=0;
}

849 · Basic Calculator III Algorithms Hard Description

Implement a basic calculator to evaluate a simple expression string.

The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces .

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

You may assume that the given expression is always valid. All intermediate results will be in the range of [-2147483648, 2147483647]

Do not use the eval built-in library function.

Example

Example 1:

Input："1 + 1"
Output：2
Explanation：1 + 1 = 2

Example 2:

Input：" 6-4 / 2 "
Output：4
Explanation：4/2=2，6-2=4

public class Solution {
    private int i=0;
    public int calculate(String s) {
        Stack stack = new Stack();
        int num = 0;
        char op = '+';
        while(i<s.length()){
            char c= s.charAt(i++);
            if(c>='0' && c<='9') num = num*10 + (c-'0');
            if(c=='(') num = calculate(s);
            if(i==s.length() || c=='+' || c=='-' || c=='*' || c=='/' || c==')'){
                if(op=='+') stack.push(num);
                else if(op=='-') stack.push(-num);
                else if(op=='*') stack.push(stack.pop()*num);
                else if(op=='/') stack.push(stack.pop()/num);
                num = 0;
                op=c;
            }
            if(c==')') break;
        }
        int sum = 0;
        for(int n:stack) sum+=n;
        return sum;
    }
}

algrithm

经典算法一：calculator

相关

标签