问题描述
输入一个只包含加减乖除和括号的合法表达式，求表达式的值。其中除表示整除。
输入格式
输入一行，包含一个表达式。
输出格式
输出这个表达式的值。
样例输入
1-2+3*(4-5)
样例输出
-4
问题分析：
View Code
1将运算式子转化为后缀表达式
2扫描后缀表达式，将数字依次进栈，当到运算符号时，出栈两个数字，进行运算，再将结果放进数字栈中
3最后数字栈最上面得到的即为结果，边扫描边进行运算
4关键点在后缀表达式的转化，下面是后缀表达式的要求
4.1读到运算数字时，直接输出；
4.2栈为空时，读到操作符，直接进栈；
4.3左括号的优先级被视为比所有运算符低，读到左括号，直接进栈；
4.4读到右括号，把栈中左括号上面的元素输出，并把左括号弹出；
4.5读到其他运算符，输出所有优先级大于或等于该运算符的栈顶元素；
4.6最后把栈中剩余的元素一一输出。
4.7后缀表达式中没有()左右两个括号
例如该例子中5+12*(3+5)/7的后缀表达式为5 12 3 5 + * 7 / +
5有了后缀表达式进行计算
5.1、 5 12 3 5 当扫描到+时3 5 出栈进行运算得到8 在进栈 栈中现在有5 12 8
5.2、扫描到*时，12和8出栈，进行运算，得到96，进栈，栈中有5 96
5.3、扫描到7，进栈，栈中有5 96 7
5.4、扫描到/，96和7出栈，进行运算得到13.714....，进栈，栈中有5 13.714....
5.5、扫描到+，5 13.714出栈，进行运算，得到18.714....这就是结果
下面是java代码，已经在蓝桥杯系统验证成功，此算法提示是整除，所以不用考虑小数问题
1 import java.util.Collections; 2 import java.util.Scanner; 3 import java.util.Stack; 4 public class Main { 5 private Stack<String> houzhuiStack = new Stack<String>();//后缀式栈 6 private Stack<Character> yunsuanfuStack = new Stack<Character>();//运算符栈 7 private int [] operatPriority = new int[] {0,3,2,1,-1,1,0,2};//运用运算符ASCII码-40做索引的运算符优先级 8 public static void main(String[] args) { 9 Scanner scanner = new Scanner(System.in); 10 String s = scanner.nextLine(); 11 Main cal = new Main(); 12 String result = cal.calculate(s); 13 System.out.println(result); 14 } 15 /* 16 *2.得到后缀表达式进行运算 17 */ 18 public String calculate(String expression) { 19 Stack<String> resultStack = new Stack<String>(); 20 prepare(expression); 21 Collections.reverse(houzhuiStack);//将后缀式栈反转 22 String firstValue ,secondValue,currentValue;//参与计算的第一个值，第二个值和算术运算符 23 while(!houzhuiStack.isEmpty()) { 24 currentValue = houzhuiStack.pop(); 25 if(!isOperator(currentValue.charAt(0))) {//如果不是运算符则存入操作数栈中 26 resultStack.push(currentValue); 27 } else {//如果是运算符则从操作数栈中取两个值和该数值一起参与运算 28 secondValue = resultStack.pop(); 29 firstValue = resultStack.pop(); 30 String tempResult = calculate(firstValue, secondValue, currentValue.charAt(0)); 31 resultStack.push(tempResult); 32 } 33 } 34 return resultStack.pop(); 35 } 36 /** 37 * 1数据准备阶段将表达式转换成为后缀式栈 38 */ 39 private void prepare(String expression) { 40 yunsuanfuStack.push(',');//运算符放入栈底元素逗号，此符号优先级最低 41 char[] arr = expression.toCharArray(); 42 int currentIndex = 0;//当前字符的位置 43 int count = 0;//上次算术运算符到本次算术运算符的字符的长度便于或者之间的数值 44 char currentOp ,peekOp;//当前操作符和栈顶操作符 45 for(int i=0;i<arr.length;i++) { 46 currentOp = arr[i]; 47 if(isOperator(currentOp)) {//如果当前字符是运算符 48 if(count > 0) { 49 houzhuiStack.push(new String(arr,currentIndex,count));//取两个运算符之间的数字 50 } 51 peekOp = yunsuanfuStack.peek(); 52 if(currentOp == ')') {//遇到反括号则将运算符栈中的元素移除到后缀式栈中直到遇到左括号 53 while(yunsuanfuStack.peek() != '(') { 54 houzhuiStack.push(String.valueOf(yunsuanfuStack.pop())); 55 } 56 yunsuanfuStack.pop(); 57 } else { 58 while(currentOp != '(' && peekOp != ',' && compare(currentOp,peekOp) ) { 59 houzhuiStack.push(String.valueOf(yunsuanfuStack.pop())); 60 peekOp = yunsuanfuStack.peek(); 61 } 62 yunsuanfuStack.push(currentOp); 63 } 64 count = 0; 65 currentIndex = i+1; 66 } else { 67 count++; 68 } 69 } 70 if(count > 1 || (count == 1 && !isOperator(arr[currentIndex]))) {//最后一个字符不是括号或者其他运算符的则加入后缀式栈中 71 houzhuiStack.push(new String(arr,currentIndex,count)); 72 } 73 74 while(yunsuanfuStack.peek() != ',') { 75 houzhuiStack.push(String.valueOf( yunsuanfuStack.pop()));//将操作符栈中的剩余的元素添加到后缀式栈中 76 } 77 } 78 /** 79 * 判断是否为算术符号 80 */ 81 private boolean isOperator(char c) { 82 return c == '+' || c == '-' || c == '*' || c == '/' || c == '(' ||c == ')'; 83 } 84 /** 85 * 利用ASCII码-40做下标去算术符号优先级 86 */ 87 public boolean compare(char cur,char peek) {// 如果是peek优先级高于cur，返回true，默认都是peek优先级要低 88 boolean result = false; 89 if(operatPriority[(peek)-40] >= operatPriority[(cur) - 40]) { 90 result = true; 91 } 92 return result; 93 } 94 /** 95 * 按照给定的算术运算符做计算 96 */ 97 private String calculate(String firstValue,String secondValue,char currentOp) { 98 String result = ""; 99 switch(currentOp) { 100 case '+': 101 result = String.valueOf(ArithHelper.add(firstValue, secondValue)); 102 break; 103 case '-': 104 result = String.valueOf(ArithHelper.sub(firstValue, secondValue)); 105 break; 106 case '*': 107 result = String.valueOf(ArithHelper.mul(firstValue, secondValue)); 108 break; 109 case '/': 110 result = String.valueOf(ArithHelper.div(firstValue, secondValue)); 111 break; 112 } 113 return result; 114 } 115 static class ArithHelper { 116 // 这个类不能实例化 117 private ArithHelper() { 118 } 119 /** 120 * 提供精确的加法运算。 121 * @param v1 被加数 122 * @param v2 加数 123 * @return 两个参数的和 124 */ 125 public static String add(String v1, String v2) { 126 java.math.BigDecimal b1 = new java.math.BigDecimal(v1); 127 java.math.BigDecimal b2 = new java.math.BigDecimal(v2); 128 return String.valueOf(b1.add(b2).intValue()); 129 } 130 /** 131 * 提供精确的减法运算。 132 * @param v1 被减数 133 * @param v2 减数 134 * @return 两个参数的差 135 */ 136 public static String sub(String v1, String v2) { 137 java.math.BigDecimal b1 = new java.math.BigDecimal(v1); 138 java.math.BigDecimal b2 = new java.math.BigDecimal(v2); 139 return String.valueOf(b1.subtract(b2).intValue()); 140 } 141 /** 142 * 提供精确的乘法运算。 143 * @param v1 144 * 被乘数 145 * @param v2 146 * 乘数 147 * @return 两个参数的积 148 */ 149 public static String mul(String v1, String v2) { 150 java.math.BigDecimal b1 = new java.math.BigDecimal(v1); 151 java.math.BigDecimal b2 = new java.math.BigDecimal(v2); 152 return String.valueOf(b1.multiply(b2).intValue()); 153 } 154 /** 155 * 提供（相对）精确的除法运算，当发生除不尽的情况时，精确到 小数点以后10位，以后的数字四舍五入。 156 * @param v1 157 * 被除数 158 * @param v2 159 * 除数 160 * @return 两个参数的商 161 */ 162 public static String div(String v1, String v2) { 163 java.math.BigDecimal b1 = new java.math.BigDecimal(v1); 164 java.math.BigDecimal b2 = new java.math.BigDecimal(v2); 165 return String.valueOf(b1.divideToIntegralValue(b2).intValue()); 166 } 167 } 168 }
下面的代码是考虑了不识字整除的情况。仅供参考
1 import java.util.Collections; 2 import java.util.Scanner; 3 import java.util.Stack; 4 public class 表达式求值 { 5 private Stack<String> houzhuiStack = new Stack<String>();//后缀式栈 6 private Stack<Character> yunsuanfuStack = new Stack<Character>();//运算符栈 7 private int [] operatPriority = new int[] {0,3,2,1,-1,1,0,2};//运用运算符ASCII码-40做索引的运算符优先级 8 public static void main(String[] args) { 9 Scanner scanner = new Scanner(System.in); 10 String s = scanner.nextLine(); 11 表达式求值 cal = new 表达式求值(); 12 double result = cal.calculate(s); 13 System.out.println(result); 14 } 15 /* 16 *2.得到后缀表达式进行运算 17 */ 18 public double calculate(String expression) { 19 Stack<String> resultStack = new Stack<String>(); 20 prepare(expression); 21 Collections.reverse(houzhuiStack);//将后缀式栈反转 22 String firstValue ,secondValue,currentValue;//参与计算的第一个值，第二个值和算术运算符 23 while(!houzhuiStack.isEmpty()) { 24 currentValue = houzhuiStack.pop(); 25 if(!isOperator(currentValue.charAt(0))) {//如果不是运算符则存入操作数栈中 26 resultStack.push(currentValue); 27 } else {//如果是运算符则从操作数栈中取两个值和该数值一起参与运算 28 secondValue = resultStack.pop(); 29 firstValue = resultStack.pop(); 30 String tempResult = calculate(firstValue, secondValue, currentValue.charAt(0)); 31 resultStack.push(tempResult); 32 } 33 } 34 return Double.valueOf(resultStack.pop()); 35 } 36 37 /** 38 * 1数据准备阶段将表达式转换成为后缀式栈 39 */ 40 private void prepare(String expression) { 41 yunsuanfuStack.push(',');//运算符放入栈底元素逗号，此符号优先级最低 42 char[] arr = expression.toCharArray(); 43 int currentIndex = 0;//当前字符的位置 44 int count = 0;//上次算术运算符到本次算术运算符的字符的长度便于或者之间的数值 45 char currentOp ,peekOp;//当前操作符和栈顶操作符 46 for(int i=0;i<arr.length;i++) { 47 currentOp = arr[i]; 48 if(isOperator(currentOp)) {//如果当前字符是运算符 49 if(count > 0) { 50 houzhuiStack.push(new String(arr,currentIndex,count));//取两个运算符之间的数字 51 } 52 peekOp = yunsuanfuStack.peek(); 53 if(currentOp == ')') {//遇到反括号则将运算符栈中的元素移除到后缀式栈中直到遇到左括号 54 while(yunsuanfuStack.peek() != '(') { 55 houzhuiStack.push(String.valueOf(yunsuanfuStack.pop())); 56 } 57 yunsuanfuStack.pop(); 58 } else { 59 while(currentOp != '(' && peekOp != ',' && compare(currentOp,peekOp) ) { 60 houzhuiStack.push(String.valueOf(yunsuanfuStack.pop())); 61 peekOp = yunsuanfuStack.peek(); 62 } 63 yunsuanfuStack.push(currentOp); 64 } 65 count = 0; 66 currentIndex = i+1; 67 } else { 68 count++; 69 } 70 } 71 if(count > 1 || (count == 1 && !isOperator(arr[currentIndex]))) {//最后一个字符不是括号或者其他运算符的则加入后缀式栈中 72 houzhuiStack.push(new String(arr,currentIndex,count)); 73 } 74 75 while(yunsuanfuStack.peek() != ',') { 76 houzhuiStack.push(String.valueOf( yunsuanfuStack.pop()));//将操作符栈中的剩余的元素添加到后缀式栈中 77 } 78 } 79 80 /** 81 * 判断是否为算术符号 82 */ 83 private boolean isOperator(char c) { 84 return c == '+' || c == '-' || c == '*' || c == '/' || c == '(' ||c == ')'; 85 } 86 87 /** 88 * 利用ASCII码-40做下标去算术符号优先级 89 */ 90 public boolean compare(char cur,char peek) {// 如果是peek优先级高于cur，返回true，默认都是peek优先级要低 91 boolean result = false; 92 if(operatPriority[(peek)-40] >= operatPriority[(cur) - 40]) { 93 result = true; 94 } 95 return result; 96 } 97 98 /** 99 * 按照给定的算术运算符做计算 100 */ 101 private String calculate(String firstValue,String secondValue,char currentOp) { 102 String result = ""; 103 switch(currentOp) { 104 case '+': 105 result = String.valueOf(ArithHelper.add(firstValue, secondValue)); 106 break; 107 case '-': 108 result = String.valueOf(ArithHelper.sub(firstValue, secondValue)); 109 break; 110 case '*': 111 result = String.valueOf(ArithHelper.mul(firstValue, secondValue)); 112 break; 113 case '/': 114 result = String.valueOf(ArithHelper.div(firstValue, secondValue)); 115 break; 116 } 117 return result; 118 } 119 120 static class ArithHelper { 121 // 默认除法运算精度 122 private static final int DEF_DIV_SCALE = 16; 123 // 这个类不能实例化 124 private ArithHelper() { 125 } 126 127 /** 128 * 提供精确的加法运算。 129 * @param v1 被加数 130 * @param v2 加数 131 * @return 两个参数的和 132 */ 133 134 public static double add(double v1, double v2) { 135 java.math.BigDecimal b1 = new java.math.BigDecimal(Double.toString(v1)); 136 java.math.BigDecimal b2 = new java.math.BigDecimal(Double.toString(v2)); 137 return b1.add(b2).doubleValue(); 138 } 139 140 public static double add(String v1, String v2) { 141 java.math.BigDecimal b1 = new java.math.BigDecimal(v1); 142 java.math.BigDecimal b2 = new java.math.BigDecimal(v2); 143 return b1.add(b2).doubleValue(); 144 } 145 146 /** 147 * 提供精确的减法运算。 148 * @param v1 被减数 149 * @param v2 减数 150 * @return 两个参数的差 151 */ 152 153 public static double sub(double v1, double v2) { 154 java.math.BigDecimal b1 = new java.math.BigDecimal(Double.toString(v1)); 155 java.math.BigDecimal b2 = new java.math.BigDecimal(Double.toString(v2)); 156 return b1.subtract(b2).doubleValue(); 157 } 158 159 public static double sub(String v1, String v2) { 160 java.math.BigDecimal b1 = new java.math.BigDecimal(v1); 161 java.math.BigDecimal b2 = new java.math.BigDecimal(v2); 162 return b1.subtract(b2).doubleValue(); 163 } 164 165 /** 166 * 提供精确的乘法运算。 167 * @param v1 168 * 被乘数 169 * @param v2 170 * 乘数 171 * @return 两个参数的积 172 */ 173 174 public static double mul(double v1, double v2) { 175 java.math.BigDecimal b1 = new java.math.BigDecimal(Double.toString(v1)); 176 java.math.BigDecimal b2 = new java.math.BigDecimal(Double.toString(v2)); 177 return b1.multiply(b2).doubleValue(); 178 } 179 180 public static double mul(String v1, String v2) { 181 java.math.BigDecimal b1 = new java.math.BigDecimal(v1); 182 java.math.BigDecimal b2 = new java.math.BigDecimal(v2); 183 return b1.multiply(b2).doubleValue(); 184 } 185 186 /** 187 * 提供（相对）精确的除法运算，当发生除不尽的情况时，精确到 小数点以后10位，以后的数字四舍五入。 188 * @param v1 189 * 被除数 190 * @param v2 191 * 除数 192 * @return 两个参数的商 193 */ 194 195 public static double div(double v1, double v2) { 196 return div(v1, v2, DEF_DIV_SCALE); 197 } 198 199 public static double div(String v1, String v2) { 200 java.math.BigDecimal b1 = new java.math.BigDecimal(v1); 201 java.math.BigDecimal b2 = new java.math.BigDecimal(v2); 202 return b1.divide(b2, DEF_DIV_SCALE, java.math.BigDecimal.ROUND_HALF_UP).doubleValue(); 203 } 204 205 /** 206 * 提供（相对）精确的除法运算。当发生除不尽的情况时，由scale参数指 定精度，以后的数字四舍五入。 207 * @param v1 被除数 208 * @param v2 除数 209 * @param scale 表示表示需要精确到小数点以后几位。 210 * @return 两个参数的商 211 */ 212 213 public static double div(double v1, double v2, int scale) { 214 if (scale < 0) { 215 throw new IllegalArgumentException("The scale must be a positive integer or zero"); 216 } 217 java.math.BigDecimal b1 = new java.math.BigDecimal(Double.toString(v1)); 218 java.math.BigDecimal b2 = new java.math.BigDecimal(Double.toString(v2)); 219 return b1.divide(b2, scale, java.math.BigDecimal.ROUND_HALF_UP).doubleValue(); 220 } 221 222 /** 223 * 提供精确的小数位四舍五入处理。 224 * @param v 需要四舍五入的数字 225 * @param scale 小数点后保留几位 226 * @return 四舍五入后的结果 227 */ 228 229 public static double round(double v, int scale) { 230 if (scale < 0) { 231 throw new IllegalArgumentException("The scale must be a positive integer or zero"); 232 } 233 java.math.BigDecimal b = new java.math.BigDecimal(Double.toString(v)); 234 java.math.BigDecimal one = new java.math.BigDecimal("1"); 235 return b.divide(one, scale, java.math.BigDecimal.ROUND_HALF_UP).doubleValue(); 236 } 237 238 public static double round(String v, int scale) { 239 if (scale < 0) { 240 throw new IllegalArgumentException("The scale must be a positive integer or zero"); 241 } 242 java.math.BigDecimal b = new java.math.BigDecimal(v); 243 java.math.BigDecimal one = new java.math.BigDecimal("1"); 244 return b.divide(one, scale, java.math.BigDecimal.ROUND_HALF_UP).doubleValue(); 245 } 246 } 247 }