描述
- 请写一个整数计算器，支持加减乘三种运算和括号。
方法一
思路
栈，递归，后缀表达式与中缀表达式
首先说明没有考虑数据为负数的情况，测试数据中也没有与负数相关的数据。
后缀表达式又叫做逆波兰式，其是将运算符写在操作数之后，后缀表达式的计算要比中缀表达式简单，所以考虑先将中缀表达式转换成后缀表达式。
转换过程如下：
1.初始化运算符栈，创建后缀字符串；
2.从左至右遍历中缀表达式；
3.遇到操作数输出至后缀字符串中；
4.遇到运算符时，比较其与栈顶运算符的优先级：- 如果栈空或栈顶元素为'('，则当前运算符直接入栈；
- 若栈顶元素优先级较低，当前运算符直接入栈；
- 反之，弹出栈顶元素，输入到后缀字符串中，再次转到步骤4，与新的栈顶元素进行比较。
5.遍历到'('时，直接入栈；
6.遍历到')'时，依次输出栈中操作符至后缀字符串中直到遇到左括号，将这一对括号丢弃；
7.重复步骤2至6，直至遍历完成；
8.依次将栈中元素输出至后缀字符串中，所得字符串即为后缀字符串。参考下图示例：
接下来就是后缀表达式的求值了，从左至右遍历后缀表达式，遇到数字时，将数字压入栈中，遇到运算符时，弹出栈顶的两个元素，使用运算进行相应的计算，并将结果重新入栈，重复上述操作直至遍历结束，最后运算得出的值即为表达式的结果。
这里得说明一下，由于题目所给的表达式，其运算数值是多位数的，所以在将中缀表达式转换成后缀表达式时，需要在操作数之间添加一个空格，以便在计算时能够清楚的分辨出操作数。
代码如下：
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* 返回表达式的值
* @param s string字符串 待计算的表达式
* @return int整型
*/
public int solve (String s) {
// 转换成后缀表达式
s = postfix(s);
// 后缀表达式求值
return postCompute(s);
}
/**
* 将中缀表达式转换为后缀表达式
* @param s 中缀表达式
* @return String字符串 后缀表达式
*/
private String postfix(String s){
// 后缀表达式
StringBuilder sb = new StringBuilder();
Stack<Character> ops = new Stack<>();
int i = 0;
while(i < s.length()){
char c = s.charAt(i++);
if (c == '(' || c == '+' || c == '-' || c == '*'){
// 加一个空格是为了将操作数之间隔开
sb.append(" ");
pushOP(sb,c,ops);
continue;
}
if (c == ')'){
// 弹出操作符直到(
while(ops.peek() != '('){
sb.append(ops.pop());
}
ops.pop();
continue;
}
sb.append(c);
}
// 弹出栈中元素
while(!ops.isEmpty()){
sb.append(ops.pop());
}
return sb.toString();
}
private void pushOP(StringBuilder sb,char op,Stack<Character> ops){
// 栈空，或者栈顶元素为(,操作符直接放入栈中
if (ops.isEmpty() || ops.peek() == '(' || op == '('){
ops.add(op);
return;
}
char c = ops.peek();
// 栈顶操作符的优先级低于当前操作符，直接压入栈中
if (c != '*' && op == '*'){
ops.add(op);
return;
}
// 否则，弹出栈顶元素，继续比较
c = ops.pop();
sb.append(c);
pushOP(sb,op,ops);
}
/**
* 后缀表达式计算
* @param s 后缀表达式
* @return int 计算结果
*/
private int postCompute(String s){
Stack<Integer> stack = new Stack<>();
int i = 0;
while(i < s.length()){
char c = s.charAt(i++);
if (c == ' '){
continue;
}
// 加减乘运算
else if (c == '*'){
int multi = stack.pop() * stack.pop();
stack.add(multi);
}else if (c == '-'){
int a = stack.pop();
int b = stack.pop();
stack.add(b-a);
}else if (c == '+'){
int sum = stack.pop() + stack.pop();
stack.add(sum);
}else {
StringBuilder num = new StringBuilder();
num.append(c);
c = s.charAt(i++);
// 字符串转换成int整数
while(c >= '0' && c <= '9'){
num.append(c);
c = s.charAt(i++);
}
--i;
stack.add(Integer.valueOf(num.toString()));
}
}
return stack.pop();
}
}- 时间复杂度：
,转后缀以及计算均只需要
- 空间复杂度：
方法二
思路
中缀表达式，栈
首先还是不考虑带负号的数据。
方法一先求后缀表达式再计算，其实是可以直接对中缀表达式进行计算的，计算过程如下：
1.初始化运算符栈以及操作数栈；
2.从左至右遍历中缀表达式；
3.遇到操作数，将操作数压入操作数栈；
4.遇到运算符，比较其与运算符栈顶元素的优先级：- 如果栈顶元素为空，或者是左括号'('，则直接入栈；
- 若栈顶元素优先级高或者是同级，弹出栈顶元素，弹出操作数栈中栈顶的两个元素进行相应运算，结果如操作数栈，重新进行4的操作；
- 反之，则当前运算符入运算符栈；
5.遇到左括号，直接入栈；
6.遇到右括号，弹出栈中元素直至碰到左括号，当然在弹出运算符栈中元素时，需要同时进行相应的运算；
7.遍历完成，弹出运算符栈中元素，进行相应的运算，操作数中的最终元素即为中缀表达式的计算值。参考下图示例：
代码如下：
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * 返回表达式的值 * @param s string字符串 待计算的表达式 * @return int整型 */ public int solve (String s) { if (s == null || s.length() == 0){ return 0; } return compute(s); } /** * 中缀表达式计算 * @param s 后缀表达式 * @return int 计算结果 */ private int compute(String s){ Stack<Character> ops = new Stack<>(); Stack<Integer> nums = new Stack<>(); int i = 0; while(i < s.length()){ char c = s.charAt(i); // 加减乘运算 if (c == '*'){ // 乘法入栈 ops.add(c); ++i; }else if (c == '-'){ // 优先级高的或者同是减号的栈中操作优先计算 while(!ops.isEmpty() &&( ops.peek() == '*' || ops.peek() == '-')){ calculate(nums,ops.pop()); } ops.add(c); ++i; }else if (c == '+'){ while(!ops.isEmpty() && ops.peek() == '*'){ calculate(nums,ops.pop()); } ops.add(c); ++i; }else if (c == '('){ ops.add(c); ++i; }else if (c == ')'){ while(ops.peek() != '('){ calculate(nums,ops.pop()); } // 弹出'(' ops.pop(); ++i; }else { // 转换数字 StringBuilder num = new StringBuilder(""); int len = s.length(); while(c >= '0' && c <= '9'){ num.append(c); ++i; if (i >= len){ break; } c = s.charAt(i); } nums.add(Integer.valueOf(num.toString())); } } while(!ops.isEmpty()){ calculate(nums,ops.pop()); } return nums.pop(); } /** * 实现四则运算 * @param nums 操作数栈 * @param op 操作符 */ private void calculate(Stack<Integer> nums,char op){ int a = nums.pop(); int b = nums.pop(); if (op == '*'){ nums.add(a*b); return; } if (op == '+'){ nums.add(a+b); return; } nums.add(b-a); } }时间复杂度：
空间复杂度：
那么如何处理带负号的数据呢？
首先负号主要在哪出现呢？
1.首位
2.括号内的首位
3.其他位置的负号都可以当做减号所以只需要在上述的两个位置将减号转换成负号即可。
只需要在方法二的代码中在数字转换阶段添一个负数判断即可，如下：
boolean minus = false; // 判断是否为负数 if (i == 1){ if (s.charAt(i-1) == '-'){ minus = true; } } if (i > 1){ if (s.charAt(i-1) == '-' && s.charAt(i-2) == '('){ minus = true; } } // 转换数字 StringBuilder num = new StringBuilder(""); int len = s.length(); while(c >= '0' && c <= '9'){ num.append(c); ++i; if (i >= len){ break; } c = s.charAt(i); } int n = Integer.valueOf(num.toString()); if (minus){ n = 0 - n; // 弹出负号 ops.pop(); } nums.add(n);
京公网安备 11010502036488号