LeetCode224. 基本计算器

深藏阁楼爱情的钟 2022-11-07 04:12 162阅读 0赞

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

示例 1：
    
    输入：s = "1 + 1"
    输出：2
    示例 2：
    
    输入：s = " 2-1 + 2 "
    输出：3
    示例 3：
    
    输入：s = "(1+(4+5+2)-3)+(6+8)"
    输出：23
     
    
    提示：
    
    1 <= s.length <= 3 * 105
    s 由数字、'+'、'-'、'('、')'、和 ' ' 组成
    s 表示一个有效的表达式
    
    来源：力扣（LeetCode）
    链接：https://leetcode-cn.com/problems/basic-calculator
    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：  
1、将字符串所有空格删除  
2、由于运算符号只有‘+’，‘-’，‘（’，‘）’，我们可以考虑去除符号，当‘（‘前面符号为‘-’时，则该（）符号内所有运算需要改变运算符号，即+变为-，-变为+，所以，我们需要一个符号栈来记录（）前的符号。  
3、当记录（）前的符号后，我们只需要将所有数字符号转化为数值符号，然后每一次运算时，加上符号栈相应的符号即可。

class Solution {
        
    	 public int calculate(String s) {
        
    		 s=s.replaceAll(" ", "");
    		 Stack<Integer> stack=new Stack<>();
    		 stack.push(1);
    		 int res=0;
    		 int sign=1;
    		 for(int i=0;i<s.length();i++) {
        
    			 if(s.charAt(i)=='+') {
        
    				 sign=stack.peek();
    			 }else if(s.charAt(i)=='-') {
        
    				 sign=-stack.peek();
    			 }else if(s.charAt(i)=='(') {
        
    				 stack.push(sign);
    			 }else if(s.charAt(i)==')') {
        
    				 stack.pop();
    			 }else {
        
    				 int num=0;
    				 while(i<s.length()) {
        
    					 if(Character.isDigit(s.charAt(i))) {
        
    						 num=num*10+s.charAt(i)-'0';
    						 i++;
    					 }
    					 else {
        
    						 i--;
    						 break;
    					 }
    				 }
    				 res+=sign*num;
    			 }
    		 }
    		 return res;
    	 }
    }