【编程题】简单的四则运算

问题描述：输入一个只包含个位数字的简单四则运算表达式字符串，计算该表达式的值
注： 1、表达式只含 +, -, *, /, (, ), 四则运算符
2、表达式数值只包含个位整数(0-9)，且不会出现0作为除数的情况
3、要考虑加减乘除按通常四则运算规定的计算优先级
4、除法用整数除法，即仅保留除法运算结果的整数部分。比如8/3=2。输入表达式保证无0作为除数情况发生
5、输入字符串一定是符合题意合法的表达式，其中只包括数字字符和四则运算符字符，除此之外不含其它任何字符，不会出现计算溢出情况
• 要求实现函数：
int calculate(int len,char *expStr)
【输入】 int len: 字符串长度；
char *expStr: 表达式字符串；
【输出】无
【返回】计算结果

• 示例
1）输入：char *expStr = “1+4*5-8/3”
函数返回：19
2）输入：char *expStr = “8/3*3”
函数返回：6

  1 package MyTest;
  2 
  3 /**
  4  * 简单的四则运算，每个参与运算的数字都在0-9之间。
  5  */
  6 
  7 import java.util.*;
  8 
  9 public class FourOps {
 10 
 11     public static void main(String[] args) {
 12         Scanner in = new Scanner(System.in);
 13         while(in.hasNext()){
 14             String expretion = in.next();
 15             int length = expretion.length();
 16             int result = compute(length, expretion);
 17             System.out.println(result);
 18         }
 19 
 20     }
 21     
 22     /**
 23      * 该函数有两个功能
 24      * 1. 首先把一个正常的中缀表达式，转化为一个后缀表达式
 25      * 2. 通过后缀表达式计算表达式的值
 26      * @param length
 27      * @param expretion
 28      * @return
 29      */
 30     private static int compute(int length, String expretion) {
 31         int result = 0;
 32         List<Character> oneOps = new LinkedList<>();
 33         oneOps.add('+');
 34         oneOps.add('-');
 35         List<Character> twoOps = new LinkedList<>();
 36         twoOps.add('*');
 37         twoOps.add('/');
 38         LinkedList<Character> ops = new LinkedList<>(); //用作栈，前面一定也要是LinkedList
 39         StringBuffer changedExp = new StringBuffer();
 40         for(int i = 0; i < length; i++){
 41             Character temp = expretion.charAt(i);
 42             if(temp >= '0' && temp <= '9')
 43                 changedExp.append(temp);
 44             else{
 45                 if(ops.isEmpty())
 46                     ops.push(temp);
 47                 else{
 48                     if(temp == '(')
 49                         ops.push(temp);
 50                     else{
 51                         if(oneOps.contains(temp)){
 52 //                            if(ops.peek() != '(')
 53                             //原来用的if，考虑在遇到+-的时候应该把栈里的运算符都pop出来，现在改用while
 54                             while(!ops.isEmpty()){
 55                                 if(ops.peek() == '(')
 56                                     break;
 57                                 changedExp.append(ops.pop());
 58                             }                                    
 59                             ops.push(temp);
 60                         }
 61                         else if(twoOps.contains(temp) && twoOps.contains(ops.peek())){    //为了连续的/法
 62                             changedExp.append(ops.pop());
 63                             ops.push(temp);
 64                         }
 65                         else if(temp != ')'){
 66                             ops.push(temp);
 67                         }
 68                         else{    //')'的情况
 69                             while(ops.peek() != '('){
 70                                 changedExp.append(ops.pop());
 71                             }
 72                             ops.pop();
 73                         }
 74                     }
 75                 }
 76             }
 77         }
 78         while(!ops.isEmpty()){
 79             changedExp.append(ops.pop());
 80         }
 81         String changedExpStr = changedExp.toString();
 82         System.out.println(changedExpStr);    //输出转化后的后缀表达式
 83         
 84         //用后缀表达式计算
 85         LinkedList<Integer> nums = new LinkedList<>();
 86         for(int i = 0; i < changedExpStr.length(); i++){
 87             Character temp = changedExpStr.charAt(i);
 88             if(temp >= '0' && temp <= '9'){
 89                 nums.push(temp-'0');
 90             }
 91             else{
 92                 int a = nums.pop();
 93                 int b = nums.pop();
 94                 switch(temp){
 95                 case '+': nums.push(a+b); break;
 96                 case '-': nums.push(b-a); break;
 97                 case '*': nums.push(a*b); break;
 98                 case '/': nums.push(b/a); break;
 99                 }
100             }
101         }
102         result = nums.pop();
103         return result;
104     }
105 
106 }