赞
踩
给你一个字符串表达式 s
,请你实现一个基本计算器来计算并返回它的值。
整数除法仅保留整数部分。
示例 1:
输入:s = "3+2*2"
输出:7
示例 2:
输入:s = " 3/2 "
输出:1
示例 3:
输入:s = " 3+5 / 2 "
输出:5
提示:
本题与224.基本计算器相比,加入了乘法运算和除法运算,由此出现了一个问题,如何维护运算符的优先级?为了能够复用224题的代码,这里我选择的策略是,先进行乘除法的计算,等遇到右括号或者扫描完毕后,统一计算加减法。
同样,这里我们使用两个栈 number 和 symbol。分别用来存放操作数和操作符。
对字符串进行一次扫描,规则如下:
如果为空格,直接跳过。
如果为‘+’、‘-’、‘(’、‘*’、‘/’,则直接入栈。
如果为‘)’,则依次将符号栈的栈顶元素出栈,将数字栈中的操作数出栈,然后进行计算,计算后将结果存入数字栈,直到出栈符号为左括号时停止出栈。
如果为数字,则首先继续扫描字符串,获得完整的数字。然后,根据符号栈栈顶元素进行不同的操作。如果是乘除法,则数字栈顶元素出栈,进行计算后将结果存入数字栈。如果为加号或左括号,则将操作数入栈。如果减号,则将操作数的相反数入栈。
扫描结束后,符号栈内可能还有一些加号未运算,需要依次出栈并求和,得到最终结果。
这里同样需要注意几个问题:
第一,可能出现第一个数为负数,为了避免边界判断,我们在扫描前向数字栈入栈元素0。
第二,左括号后的第一个数可能是负数,我们选择将 “(-” 替换为 “(0-”。
实现代码如下,空间复杂度O(n),时间复杂度O(n)。运行时间258 ms。
class Solution { public int calculate(String s) { int n = s.length(); char[] exp = s.toCharArray(); Stack<Character> symbol = new Stack<Character>(); Stack<Integer> number = new Stack<Integer>(); // 防止第一个数为负数 number.push(0); // 将 (- 替换为 (0- s = s.replaceAll("\\(-", "(0-"); int i = 0; while (i < n) { char c = exp[i++]; if (c == ' ') { continue; } else if (c == '+' || c == '-' || c == '(' || c == '*' || c == '/') { symbol.push(c); } else { // 获取操作数 int num; if (c == ')') { num = number.pop(); char op = symbol.pop(); while (op != '(') { int num2 = number.pop(); System.out.println(num + " " + num2); if (op == '+') { num = num2 + num; }else if(op == '-'){ num = num2 - num; } op = symbol.pop(); }; } else { num = c - '0'; while (i < n && Character.isDigit(exp[i])) { num = 10 * num + exp[i++] - '0'; } } // 若符号栈空, 则将操作数压栈 System.out.println("num:" + num); if (symbol.isEmpty()) { number.push(num); } else { // 如果符号栈顶元素为运算符,则进行计算,并将结果压栈,如果为(,则直接将操作数压栈 char top = symbol.peek(); if (top == '*') { symbol.pop(); number.push((number.pop() * num)); } else if (top == '/') { symbol.pop(); number.push((number.pop() / num)); } else if (top == '-') { symbol.pop(); symbol.push('+'); number.push(-1 * num); } else { number.push(num); } } } System.out.println("number:" + number.toString()); System.out.println("symbol:" + symbol.toString()); System.out.println(); } // 对栈内元素累加 while (!symbol.isEmpty()) { symbol.pop(); number.push(number.pop() + number.pop()); } return number.pop(); } }
此题为了224题的代码能够复用,其实是采取了一个投机取巧的办法。事实上,计算应该发生在读取到符号时,而不是读取到数字时。
选择在读取数字时计算,思路就是要根据该数字前的最后一个操作符计算出结果,然后将结果计算出并压栈,但是在有多个优先级的运算符时,往往需要考虑该数字后的第一个操作符的优先级问题,就会比较复杂,难以判断。
一个好的思路就是在读取到符号时进行计算。首先定义一个字典类型,表示不同运算符的优先级。如果读取到运算符op,则将op之前直到左括号的所有优先级大于等于op的运算符出栈并计算;如果读取到右括号,则将直到左括号的所有运算符依次出栈并计算。这样做的好处就是保证了在同一括号内,运算符的优先级始终非严格单调递增,从而保证了结果的正确性。
另外,这样做还可以及时的处理栈内与op优先级相同的运算,防止不满足交换律的运算出错,例如 3 - 2 + 3,如果到最后一起算的话,由于栈的先入后出的特性,会先计算2+3=5,在计算3-5=-2。很明显结果不正确。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。