Basic Calculator II问题描述
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 should truncate toward zero. You may assume that the given expression is always valid. Some examples: “3+2*2” = 7 ” 3/2 ” = 1 ” 3+5 / 2 ” = 5 Note: Do not use the eval built-in library function. 意：实现字符串数学表达式的计算
算法思想
算法使用双向链表两次扫描计算（虽然不是最好的，但是思想很单纯，后续我会改进该算法，现在懒得动） 第一遍 计算 * 和 / 第二遍 计算 + 和 –
第一遍扫描，扫描字符串： – 如果当前是数字，，查看队列末尾是否为*或者/，如果是就计算当前数字和队列尾第二个数的结果，并加入队列。 – 如果当前是符号，直接加入队列末尾。 – 当第一遍扫描结束队列中剩下的就是数字和+ 、-
第二遍扫描，从头扫描队列 – 如果下一个是符号，移除并根据符号再获取下一个数值，计算结果加入队列头。
算法实现import java.util.LinkedList;public class Solution {(String s) {LinkedList<Integer> linkedList = new LinkedList<Integer>();char[] characters = s.toCharArray();char c = ‘ ‘;int k = 0;for (int i = 0; i < characters.length; i++) {c = characters[i];k = 0;if (Character.isDigit(c)) {//获取while (Character.isDigit((c = characters[i++]))) {k = (c – 48) + k * 10;if (i == characters.length)break;}//如果上一个符号为*或者/,则计算上一个数值与当前数值的操作结果if (!linkedList.isEmpty()) {if (linkedList.getLast().intValue() == 42) {linkedList.removeLast();k = linkedList.removeLast() * k;} else if (linkedList.getLast().intValue() == 47) {linkedList.removeLast();k = linkedList.removeLast() / k;}}//记录当前数值到队列中linkedList.add(k);}//如果下一个操作是+或者-，加入队列，等待下一次遍历进行计算if (i < characters.length) {if (c != ‘ ‘)linkedList.add((int) c);i–;}}int result = 0;while (!linkedList.isEmpty()) {result = linkedList.removeFirst();if (!linkedList.isEmpty()) {int op = linkedList.removeFirst().intValue();if (op == 43) {result += linkedList.removeFirst();} else {result -= linkedList.removeFirst();}linkedList.addFirst(result);}}return result;}}算法时间
O(n)
演示结果(String[] args) {System.out.println(calculate(“100+1000*1+1000/10”));}
1200
不畏不惧，不言不弃，冲破风雨的阻隔，黎明就在前方！
