讨论/《高频算法实战》 - 基本计算器/
《高频算法实战》 - 基本计算器
共 6 个回复
class Solution {
    public int calculate(String s) {
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(1);
        int res = 0, num = 0, sign = 1;
        for (char c : s.toCharArray()) {
            if (c == ' ') continue;
            if ('0' <= c && c <= '9') {
                num = num * 10 + (c - '0');
                continue;
            }
            res += sign * num;
            num = 0;
            if (c == '+') {
                sign = stack.peek();
            } else if (c == '-') {
                sign = -stack.peek();
            } else if (c == '(') {
                stack.push(sign);
            } else if (c == ')') {
                stack.pop();
            }
        }
        res += sign * num;
        return res;
    }
}
2

Java

class Solution {
    int index = 0;
    public int calculate(String s) {
        int n = 0;
        char sign = '+';
        Deque<Integer> stack = new LinkedList<>();
        for (int i = index; i < s.length(); i++) {
            char c = s.charAt(i);
            index++;
            //如果是数字则累加
            if (Character.isDigit(c)) {
                n= n*10 + (c - '0');
            }
            if (c == '(') {
                n = calculate(s);
                i = index-1;
            }
            //如果不是数字,或者是最后一位就进行压入堆栈
            if ((!Character.isDigit(c) && c !=' ') || i == s.length() - 1) {
                switch (sign) {
                    case '+':
                        stack.addFirst(n);
                        break;
                    case '-':
                        stack.addFirst(-n);
                        break;
                    case '*':
                        stack.addFirst(stack.getFirst() * n);
                        break;
                    case '/':
                        stack.addFirst(stack.getFirst() / n);
                        break;
                }
                //取当前符号,如果是最后一位则有可能不是符号
                sign = c;
                //初始化累加器
                n = 0;
            }
            if (c == ')') {
                break;
            }
        }
        int ans = 0;
        while (!stack.isEmpty()) {
            ans += stack.removeFirst();
        }
        return ans;
    }
}
1

偶遇校友hhhh,祝你新年快乐发😋

1

过年前一天来打卡,用两个栈的做法,但是这个题似乎一个栈更方便,因为有-1这种情况。。

class Solution {
public:
    int calculate(string s) {
        stack <char> ct;
        stack <int> nt;
        int n = s.length();
        int flag = 0;
        for(int i = 0 ; i < n ; i++) {
            if(s[i] == ' ')continue;
            else if(isdigit(s[i])) {
                int t = 0;
                while(i < n && (isdigit(s[i]) || s[i] == ' ')) {
                    if(isdigit(s[i]))t = t * 10 + ( s[i] - '0' );
                    i++;
                }
                nt.push(t);
                flag = 1;
                i--;
            }
            else {
                if(s[i] == '(')ct.push(s[i]);
                else {
                    if(!flag && s[i] != ')') {
                        //cout << "i = " << i << endl;
                        nt.push(0);
                    }
                    if(s[i] == '+' || s[i] == '-')flag = 0;
                    while(!ct.empty()) {
                        char c = ct.top();
                        if(c != '(' || (s[i] == ')' && c == '(') )ct.pop();
                        if(c == '(')break;
                        int x , y;
                        x = nt.top();nt.pop();
                        y = nt.top();nt.pop();
                        if(c == '+')nt.push(y + x);
                        else nt.push(y - x);
                    }
                    if(s[i] != ')')ct.push(s[i]);
                }
                
            }        
        }
        while(!ct.empty()) {
            char c = ct.top();ct.pop();
            int x , y;
            x = nt.top();nt.pop();
            y = nt.top();nt.pop();
            if(c == '+')nt.push(y + x);
            else nt.push(y - x);
        }
        return nt.top();
    }
};
1
function calculate(s: string): number {
     return new Parser(s.trim()).parse()
};

class Parser {
     private position:number = 0;
     constructor(
         private source:string
     ){}
     next = ()=> this.source[this.position];
     take = ()=>{
          const next = this.next();
          this.position++;
          return next;
     }
     isEnd(){
          if(this.position>=this.source.length){
               return true
          }
          return false;
     }
     takeWhile(fn:(char:string)=>boolean){
          let result = "";
          while(this.position<this.source.length && fn(this.next())){
              result += this.take()
          }
          return result;
     }
     skipWhiteSpace = ()=> this.takeWhile(c=>c===" " || c==="\n")

     parseIdentity = () => parseInt(this.takeWhile(c=> c.charCodeAt(0)>=48 && c.charCodeAt(0)<=57))

     parseFirst(){
           this.take() // (
           const left = this.parse()
           this.take() // )
           return left
     }

     calcu(operator:string,left:number,right:number){
          switch(operator){
               case '+':
                 return left + right
               case '-':
                 return left - right;
               default:
                return 0
          }
     }
     parse =():number=>{
         let result = 0;
         let operator = '+';
         while( !this.isEnd() && this.next()!==")"){
             this.skipWhiteSpace()
            if(!this.isEnd()){
                   switch(this.next()){
                 case '(':
                     const value = this.parseFirst()
                     result = this.calcu(operator,result,value)
                     continue
                 case '+':
                      operator = '+'
                      this.take()
                      continue
                 case '-':
                      operator = '-';
                      this.take()
                      continue
                 default:
                    const value2 = this.parseIdentity()
                     result = this.calcu(operator,result,value2)
             }
            }
             this.skipWhiteSpace()
         }
         return result
     }
}

清掉一对()时可能会剩下不止一个运算符,所以遇到+ - )就把前面的算干净比较省事

class Solution {
public:
    int calculate(string s) {
        stack<long> nums;
        stack<char> ops;
        int i = 0;
        int sz = s.size();
        int dig = 0;
        while(i<sz){
            char c = s[i];
            switch(c){
                case '+':
                case '-':
                case ')':
                    while(!ops.empty() && ops.top()!='('){
                        nums.push(computeTop(nums,ops.top()));
                        ops.pop();
                    }
                    if(c==')'){
                        ops.pop();
                    }
                    else{
                        ops.push(c);
                    }
                    break;
                case '(':
                    ops.push(c);
                    break;
                case ' ':
                    break;
                default:{
                    long digit = 0;
                    while(isdigit(s[i]) && i<sz){
                        digit *= 10;
                        digit += s[i] - '0';
                        ++i;
                    }
                    nums.push(digit);
                    continue;
                }
            }
            ++i;
        }
        return ops.empty()?nums.top():computeTop(nums,ops.top());
    }
private:
    long computeTop(stack<long> &st,char op){
        long num_right = st.top();
        st.pop();
        long num_left;
        if(!st.empty()){
            num_left = st.top();
            st.pop();
        }
        else{
            num_left = 0;
        }
        if(op=='+'){
            return num_left+num_right;
        }
        else{
            return num_left-num_right;
        }
    }
};