1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168
|
public class Calculator {
private static final String[] SUPPORT_OPERATOR = {"+", "-", "*", "/", "(", ")", "\0"};
private static final Map<String, Integer> OPERATOR_INDEX_MAP = new HashMap<>();
static { for (int i = 0; i < SUPPORT_OPERATOR.length; i++) { OPERATOR_INDEX_MAP.put(SUPPORT_OPERATOR[i], i); } }
private static final String[][] PRIORITY_TABLE = { {">", ">", "<", "<", "<", ">", ">"}, {">", ">", "<", "<", "<", ">", ">"}, {">", ">", ">", ">", "<", ">", ">"}, {">", ">", ">", ">", "<", ">", ">"}, {"<", "<", "<", "<", "<", "=", ">"}, {" ", " ", " ", " ", " ", " ", ">"}, {"<", "<", "<", "<", "<", "<", "="}, };
public static void main(String[] args) { System.out.println(solution("1 + 2")); System.out.println(solution("1 * 2 + 3")); System.out.println(solution("1 + 2 * 3")); System.out.println(solution("1 + 2 * 3 - 4 / 2 + 6 / 2 - 7"));
System.out.println(solution("1 + 2 * (3 * (1 + 2))")); }
public static int solution(String expression) { if (expression == null || expression.length() == 0) { return 0; }
Stack<Character> operatorStack = new Stack<>(); Stack<Integer> numberStack = new Stack<>(); char[] chars = expression.toCharArray();
for (int i = 0; i < chars.length; i++) { calculate(operatorStack, numberStack, String.valueOf(chars[i]), i == chars.length - 1); }
while (!operatorStack.isEmpty()) { calculate(operatorStack, numberStack, String.valueOf(numberStack.pop()), true); }
return numberStack.pop(); }
private static void calculate(Stack<Character> operatorStack, Stack<Integer> numberStack, String item, boolean isLast) { if (" ".equals(item)) { return; }
char[] items = item.toCharArray();
if (Character.isDigit(items[0])) { int itemInt = Integer.parseInt(item);
if (isLast) { int result = calculate(itemInt, Integer.parseInt(String.valueOf(numberStack.pop())), operatorStack.pop()); numberStack.push(result); } else { numberStack.push(itemInt); } } else if (OPERATOR_INDEX_MAP.containsKey(item)) { handleOperator(operatorStack, numberStack, items[0]); } else { throw new IllegalArgumentException("不支持的运算符:" + item); } }
private static void handleOperator(Stack<Character> operatorStack, Stack<Integer> numberStack, char currOperator) { if (operatorStack.isEmpty()) { operatorStack.push(currOperator); } else { Character stackChar = operatorStack.peek(); Integer stackIndex = OPERATOR_INDEX_MAP.get(String.valueOf(stackChar)); Integer currIndex = OPERATOR_INDEX_MAP.get(String.valueOf(currOperator)); String order = PRIORITY_TABLE[stackIndex][currIndex];
switch (order) { case "<": operatorStack.push(currOperator); break; case "=": operatorStack.pop(); break; case ">": int num1 = numberStack.pop(); int num2 = numberStack.pop(); numberStack.push(calculate(num1, num2, operatorStack.pop())); handleOperator(operatorStack, numberStack, currOperator); break; default: throw new IllegalArgumentException("无效的比较结果:" + order); } } }
private static int calculate(int num1, int num2, char item) { switch (String.valueOf(item)) { case "+": return num2 + num1; case "-": return num2 - num1; case "*": return num2 * num1; case "/": return num2 / num1; default: throw new UnsupportedOperationException("无效的的运算符:" + item); } } }
|