四则运算
1.想法
1.根据我们的习惯,我们先计算小括号,然后计算中括号,最后计算大括号.
2.那么我们的计算步骤
1.计算小括号中的式子结果,这个过程也是只有+-/的式子,然后将式子的string替换为结果
2.计算中括号的式子结果,这个过程也只有+-/,然后将式子的string替换为结果
3.计算中括号的式子结果,这个过程也只有+-/,然后将式子的string替换为结果
4.最后,计算只有+-/,然后将式子的string替换为结果
我们可以示例为例,3+2{1+2[-4/(8-6)+7]}
我们可以先算(8-6)的内容,然后将结果2替换(8-6)变成3+2{1+2[-4/2+7]},然后计算中括号,3+2*{1+2*5},最后计算3+2*11.最后算的示例的结果
1.我们怎么知道小括号的式子,我们找到")"->right的位置,然后找到对应这个"("->left的位置,整个string就是小括号的string
image.png
2.中括号和大括号的解法和小括号的解法一样.
3.我们怎么计算只有+-*/的式子1.先把数字和运算符分开
1.怎么把数字和运算符分开
当当前的char为'-'时,如果是index = 0或者前一个char的值为运算符时,这个值就是负号,不处理
当当前的char为'-'时,如果非前面的情况,则是减号, 1.nums.add(num) 2.ops.add(运算符)
当为其他的运算符时,数字为left->当前的index 1.nums.add(num) 2.ops.add(运算符)
image.png
分别将符号和数字存储在不同的List里面
例如:1-2*2+-1
操作符的List为{-,*,+},数字的List为{1,2,2,-1}
2.怎么将运算符和数字进行运行
分成两步计算1.计算乘除,2,计算+-
1.取出运算符A. 当为+ - 时,1.操作符为第一个或者为+-则,取下一个num和下一个操作符2.当前一个为/只取下一个操作符
例如:1-2*2+-1
操作符的List为{-,*,+},数字的List为{1,2,2,-1}
操作符为-,且前面没有操作符,此时1.将-放入新的操作符队列,2.并从数字队列中取出数字1
当取到+号的时候,前一个操作符为号,所以我们只做一件事将+号放入操作符队列
B. 当为*/时,1.操作符为第一个或者为+-则取num运算和去取下一个,数字2.前一个为*/,则取出已计算的数字和现在计算
例如:1-2*2\2
操作符的List为{-,*,\},数字的List为{1,2,2,2}
当取到第一个号时,前面的操作符为-号,那么,需要利用当前的2,和再取出下一个操作数2,计算后,放入数字列表
当取到的第一个\号,前面的符号是,所以需要先取出来原来计算2*2的结果,然后再/2
2.代码
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNextLine()) {
String line = in.nextLine();
System.out.println(calculate(line));
}
}
public static int calculate(String strExpression) {
//1.计算小括号的
int littleRight = -1;
while((littleRight = strExpression.indexOf(")"))!=-1){
int littleLeft = findLastIndex(strExpression,'(',littleRight); //左边的索引
int result = calculateSimple(strExpression.substring(littleLeft+1,littleRight));//计算之间的运算结果
String leftStr = strExpression.substring(0,littleLeft);
String rightStr = strExpression.substring(littleRight+1);
strExpression = leftStr+result+rightStr;
}
//2.计算中括号的
int midRight = -1;
while((midRight = strExpression.indexOf("]"))!=-1){
int midLeft = findLastIndex(strExpression,'[',midRight);
int result = calculateSimple(strExpression.substring(midLeft+1,midRight));
String leftStr = strExpression.substring(0,midLeft);
String rightStr = strExpression.substring(midRight+1);
strExpression = leftStr+result+rightStr;
}
//3.计算大括号的
int bigRight = -1;
while((bigRight = strExpression.indexOf("}"))!=-1){
int bigLeft = findLastIndex(strExpression,'{',bigRight);
int result = calculateSimple(strExpression.substring(bigLeft+1,bigRight));
String leftStr = strExpression.substring(0,bigLeft);
String rightStr = strExpression.substring(bigRight+1);
strExpression = leftStr+result+rightStr;
}
return calculateSimple(strExpression);
}
private static int calculateSimple(String sub) {
char[] chs = sub.toCharArray();
List<Integer> nums = new ArrayList<>();
List<Character> ops = new ArrayList<>();
int left = 0;
//分离所有的操作和数字
for(int i=0;i<chs.length;i++){
if(chs[i] == '-'&&(i-1 == -1||(chs[i-1]>'9'||chs[i-1]<'0'))){
continue;
}else if(chs[i] <'0'|| chs[i]>'9'){
nums.add(Integer.valueOf(sub.substring(left,i)));
ops.add(chs[i]);
left = i+1;
}
}
if(left<chs.length){
nums.add(Integer.valueOf(sub.substring(left)));
}
List<Integer> newNums = new ArrayList<>();
List<Character> newOps = new ArrayList<>();
int noIndex = 0,opIndex =0;
//计算所有的乘除
while(opIndex<ops.size()&&noIndex<nums.size()){
char op = ops.get(opIndex);
int num1 = nums.get(noIndex);
if (op == '+' || op == '-') {
if(opIndex-1 ==-1||ops.get(opIndex-1) =='+'||ops.get(opIndex-1)=='-') {
newOps.add(op);
newNums.add(num1);
opIndex += 1;
noIndex += 1;
}else{
newOps.add(op);
opIndex+=1;
}
}else if(op =='*'){
if(opIndex-1 !=-1&&(ops.get(opIndex-1) =='*'||ops.get(opIndex-1)=='/')) {
int num2= newNums.get(newNums.size()-1);
newNums.remove(newNums.size()-1);
num1 *= num2;
newNums.add(num1);
opIndex+=1;
noIndex+=1;
}else {
int num2 = nums.get(noIndex + 1);
num1 *= num2;
newNums.add(num1);
noIndex += 2;
opIndex += 1;
}
}else{
if(opIndex-1 !=-1&&(ops.get(opIndex-1) =='*'||ops.get(opIndex-1)=='/')) {
int num2= newNums.get(newNums.size()-1);
newNums.remove(newNums.size()-1);
num1 = num2/num1;
newNums.add(num1);
opIndex+=1;
noIndex+=1;
}else {
int num2 = nums.get(noIndex + 1);
num1 /= num2;
newNums.add(num1);
noIndex += 2;
opIndex += 1;
}
}
}
if(noIndex<nums.size()){
newNums.add(nums.get(noIndex));
}
//只剩下+-,计算其值
int temp = newNums.get(0);
for(int i=0;i<newOps.size();i++){
if(newOps.get(i) == '+'){
temp+=newNums.get(i+1);
}else{
temp-=newNums.get(i+1);
}
}
return temp;
}
//找到前一个括号的值
private static int findLastIndex(String strExpression,char c, int littleRight) {
char[] chs = strExpression.toCharArray();
for(int i=littleRight-1;i>-1;i--){
if(chs[i] == c){
return i;
}
}
return -1;
}
}
