这篇也是凑数的 ......

这篇会收录到算法通关村第四关黄金挑战里

计算器

描述 :

给定一个包含正整数、加(+)、减(-)、乘(*)、除(/)的算数表达式(括号除外)，计算其结果。

表达式仅包含非负整数，+， - ，*，/ 四种运算符和空格  。 整数除法仅保留整数部分。

题目 :

LeetCode 面试题 : 计算器 :

面试题 16.26. 计算器

分析 :

解决运算器问题，最好的工具就是栈。由于乘除优先于加减计算，因此不妨考虑先进行所有乘除运算，并将这些乘除运算后的整数值放回原表达式的相应位置，则随后整个表达式的值，就等于一系列整数加减后的值。基于此，我们可以用一个栈，保存这些(进行乘除运算后的)整数的值。

对于加减号后的数字，将其直接压入栈中;对于乘除号后的数字，可以直接与栈顶元素计算，并替换栈顶元素为计算后的结果具体来说，遍历字符串 ss，并用变量flag 记录每个数字之前的运算符，对于第一个数字，其之前的运算符视为加号。每次遍历到数字末尾时，根据 flag 来决定计算方式 加号: 将数字压入栈，减号: 将数字的相反数压入栈，乘除号: 计算数字与栈顶元素，并将栈顶元素替换为计算结果。代码实现中，若读到一个运算符，或者遍历到字符串末尾，即认为是遍历到了数字末尾。处理完该数字后，更新 flag  为当前遍历的字符遍历完字符串 ss 后，将栈中元素累加，即为该字符串表达式的值。

Character.isDigit() 这个函数是判断字符是否由数字组成

举例 : 2 * 5  s="2 * 5" s的长度=5

第一步 : num = 0 , flag = '+' , 遍历 i = 0 因为是数字所以 : num = 2 

第二步 :  遍历 i = 1 , ' ' 不会进入循环

第三部 : 遍历 i = 2 , * 是乘号 所以进入到第二个分支里 , 因为默认的flag = '+' , 所以把2放到栈里 , 把符号flag = * , num = 0

第四步 : 遍历 i = 3 , ' ' 不会进入分支

第五步 : 遍历 i = 4  , num = 5 并且 i = n 所以进入第二个分支 , flag = * , 所以取出 2 * num = 2 * 5 = 10 , 把10放到栈里

解析 :

class Solution {public int calculate(String s) {Stack<Integer> stack = new Stack<>();int num = 0;int n = s.length() - 1;char flag = '+';for(int i = 0 ;i <= n ;i++){//第一个分支if(Character.isDigit(s.charAt(i))){num = num * 10 + (s.charAt(i) - '0');}//第二个分支if(!Character.isDigit(s.charAt(i)) && s.charAt(i) != ' ' || i == n){switch(flag){case '+' :stack.push(num);break;case  '-' :stack.push(-1 * num);break;case '*' :stack.push(stack.pop() * num);break;default :stack.push(stack.pop() / num);}flag = s.charAt(i);num = 0;}}int x = 0;while(!stack.isEmpty()){x += stack.pop();}return x;}
}

这期就到这里 .......