蓝桥杯算法训练 ALGO-156 表达式计算

左手的ㄟ右手 2023-10-06 09:38 84阅读 0赞

算法训练 表达式计算

时间限制：1.0s 内存限制：256.0MB

问题描述

输入一个只包含加减乖除和括号的合法表达式，求表达式的值。其中除表示整除。

输入格式

输入一行，包含一个表达式。

输出格式

输出这个表达式的值。

样例输入

1-2+3\*(4-5)

样例输出

\-4

数据规模和约定

表达式长度不超过100，表达式运算合法且运算过程都在int内进行。

**题目解析：**

**　　运算优先级： 括号 → 乘除 → 加减**

**　　例如　　1-2+3\*(4-5)**

**　　　　（1）计算（4-5），表达式变为 1-2+3\*-1**

**　　　　（2）计算 3\*-1，表达式变为 1-2+-3**

**　　　　（3）计算 1-2，表达式变为 -1+-3**

**　　　　（4）计算 -1+-3，表达式变为 -4**

**　　　　（5）结果 -4**

**　　根据这一规律，我们首先在输入的表达式两端加上括号，使程序变为重复去计算括号中的子表达式。计算规则如同上例。**

示例代码：

1 import java.io.BufferedReader;
      2 import java.io.IOException;
      3 import java.io.InputStreamReader;
      4 
      5 public class Main {
      6     public static void main(String[] args) throws IOException {
      7         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      8         StringBuilder expression = new StringBuilder("("+br.readLine()+")");    //表达式，在输入的表达式两边加上括号
      9         StringBuilder temp = new StringBuilder();                                //存放临时表达式，即每次存放的都是任意一个括号中的子表达式
     10         while(true){
     11             int frontBrackets = expression.lastIndexOf("(");            //从表达式后边开始搜索，找到最后一个"("
     12             int backBrackets = expression.indexOf(")", frontBrackets);  //从最后一个"("的位置开始往后搜索，找到与之对应的")"
     13             
     14             if(frontBrackets == -1)    break;    //若再无表达式需要计算，即expression只有一个整数时，跳出循环
     15             
     16             temp.append(expression.substring(frontBrackets + 1 , backBrackets));    //将此括号中的表达式存入temp
     17             expression.delete(frontBrackets, backBrackets + 1);        //在原始表达式中将括号连同其中的表达式删除
     18             
     19             for(int i = 0; i < temp.length(); i++){        //从子表达式中找出运算符，根据运算原则，先乘除后加减
     20                 if(temp.charAt(i) == '*'){                //若找到 "*" ，调用calculation进行运算
     21                     calculation(temp , '*' , i);
     22                     i = 0;                                //运算完后，i清零，方便下一次从开始位置继续寻找乘除运算符
     23                 }
     24                 
     25                 if(temp.charAt(i) == '/'){
     26                     calculation(temp , '/' , i);
     27                     i = 0;
     28                 }
     29             }
     30             
     31             for(int i = 0; i < temp.length(); i++){        //找完乘除运算符后，开始找加减云算符
     32                 if(temp.charAt(i) == '+'){
     33                     calculation(temp , '+' , i);
     34                     i = 0;
     35                 }
     36                 
     37                 if(temp.charAt(i) == '-'){
     38                     calculation(temp , '-' , i);
     39                     i = 0;
     40                 }
     41             }
     42             
     43             expression.insert(frontBrackets, temp);        //运算完后，将结果插入在刚才删除的括号位置，构成新的表达式，继续循环计算
     44             temp.delete(0, temp.length());                //将temp清空，方便下一个表达式计算
     45             
     46         }
     47         
     48         System.out.println(expression);        //输出结果
     49     }
     50     
     51     /**
     52      * 计算表达式
     53      * @param src  　　　　表达式
     54      * @param op   　　　　操作符
     55      * @param location    操作符在表达式中的位置
     56      */
     57     private static void calculation(StringBuilder src, char op, int location) {
     58         int x = 0;    //操作数1
     59         int y = 0;  //操作数2
     60         int sum = 0;// sum = x (op) y
     61         
     62         String check = "0123456789+-";    //检测运算符两边的内容是否为其中数组或者正数或负数
     63         StringBuilder temp = new StringBuilder();    //存放运算符两边的字符
     64         
     65         if(location == 0)    return;        //若遇到子表示其中只有加减运算符这种情况，且遇到的第一个运算符其实是想表示一个正数或者负数的符号，则函数返回，继续寻找下一个运算符
     66         
     67         int k = 0;  //搜索操作符左右两边的数
     68         for(k = location - 1; k >= 0 && check.contains(src.charAt(k) + ""); k--){    //从运算符左边一个位置开始往前搜索，找到第一个操作数
     69             try{
     70                 //若数字前边有两个运算符，第一个是为了与前边的数相连，第二个是为了表示这个数的正负，则跳出循环，执行后面的语句
     71                 //比如： 5+(7+-5*+10)，搜索到5前边时，先搜索到"-",发现前边还有一个"+"，此时temp中没有运算符，则继续执行，当搜索到"+"时，发现前边没有运算符了，就跳出循环
     72                 if((src.charAt(k) == '+' || src.charAt(k) == '-') && (src.charAt(k-1) != '+' || src.charAt(k-1) != '-' ))
     73                     break;
     74                 if(temp.charAt(0) == '+' || temp.charAt(0) == '-')
     75                     break;
     76                 
     77             }catch(Exception e){
     78 //                e.printStackTrace();    //不输出异常，满足题目输出要求
     79             }
     80             
     81             temp.insert(0, src.charAt(k));    //每次都是从temp的开始位置插入内容，保证逆向搜索的内容能按照正常的顺序存入temp
     82             src.deleteCharAt(k);            //删除运算符前边的那个数字，若有正负号，也一并删除
     83         }
     84         
     85         x = Integer.parseInt(temp.toString());    //将搜索到的此数存入x
     86         temp.delete(0, temp.length());            //将temp清空
     87         
     88         for(k = k + 2; k < src.length() && check.contains(src.charAt(k) + ""); ){    //从运算符右边一个位置开始往后搜索，找到第二个操作数，加2是因为上边的循环语句在结束时自减了一次
     89             
     90             if((src.charAt(k) == '+' || src.charAt(k) == '-') && (temp.length() != 0))
     91                 break;
     92             
     93             temp.append(src.charAt(k));
     94             src.deleteCharAt(k);
     95         }
     96         
     97         y = Integer.parseInt(temp.toString());
     98         temp.delete(0, temp.length());
     99         
    100         switch(op){
    101             case '+':
    102                 sum = x + y;
    103                 src.deleteCharAt(k-1);        //删除运算符
    104                 src.insert(k-1, sum + "");    //将结果存入src的操作符位置（此时操作符两边的数已经从src中删除，所以插入此位置相当于用结果代替子表达式，方便下一次运算）
    105                 break;
    106             
    107             case '-':
    108                 sum = x - y;
    109                 src.deleteCharAt(k-1);
    110                 src.insert(k-1, sum + "");
    111                 break;
    112                 
    113             case '*':
    114                 sum = x * y;
    115                 src.deleteCharAt(k-1);
    116                 src.insert(k-1, sum + "");
    117                 break;
    118                 
    119             case '/':
    120                 sum = x / y;
    121                 src.deleteCharAt(k-1);
    122                 src.insert(k-1, sum + "");
    123                 break;
    124             
    125             default:
    126                 break;
    127         }
    128     }
    129 }