本文共 4325 字,大约阅读时间需要 14 分钟。
前缀表达式的计算机求值
从右至左扫描表达式,遇到数字时,将数字压入堆栈,遇到运算符时,弹出栈顶的两个数,用运算符对它们做相应的计算(栈项元素和次顶元素),并将结果入栈;重复上述过程直到表达式最左端,最后运算得出的值即为表达式的结果。
例如: (3+4)X5-6 对应的前缀表达式就是- X + 3 4 5 6
,针对前缀表达式求值步骤如下: 中缀表达式的计算机求值
中缀表达式就是常见的运算表达式,如(3+4)X5-6
中缀表达式的求值是我们人最熟悉的,但是对计算机来说却不好操作,因此,在计算结果时,往往会将中缀表达式转成其它表达式来操作(一般转成后缀表达式)后缀表达式的计算机求值
从左至右扫描表达式,遇到数字时,将数字压入堆栈,遇到运算符时,弹出栈顶的两个数,用运算符对它们做相应的计算(次项元素和栈顶元素),并将结果入栈;重复上述过程直到表达式最右端,最后运算得出的值即为表达式的结果。
例如: (3+4)X5-6对应的前缀表达式就是3 4+5 X 6-,针对后缀表达式求值步骤如下:使用栈实现逆波兰表达式
在这里需要使用到俩个方法,一个是用于将表达式放入到ArrayList数组当中,方便变量,另一个是进行运算。
放入数组的方法
// 将表达式的数据放入ArrayList当中public static ListgetListString(String expression) { // 把表达式进行分割,按空格 String[] a = expression.split(" "); List list = new ArrayList (); // 把分割后的数组a放入list for (String ele : a) { list.add(ele); } return list;}
数据运算的方法
public static int Calculation(Listls) { //创建一个栈 Stack stack=new Stack (); //遍历List for(String item:ls) { //使用正则表达式判断是不是数 if (item.matches("\\d+")) { //匹配多位数 //直接入栈 stack.push(item); }else { //弹出俩个数进行运算再入栈 int num2 =Integer.parseInt(stack.pop()); int num1 =Integer.parseInt(stack.pop()); int res=0; //判断取出来的运算符符号 if (item.equals("+")) { res =num1+num2; }else if(item.equals("-")) { res =num1-num2; }else if(item.equals("*")) { res =num1*num2; }else if(item.equals("/")) { res =num1/num2; }else { throw new RuntimeException("表达式异常"); } //把res值入栈,注意数据类型 stack.push(res+""); } } //最后留在栈当中的数据就是结果 return Integer.parseInt(stack.pop());}
最后调用这俩个方法直接测试
在上面的代码当中是直接给出后缀表达式,但是这存在一个问题,后缀表达式不方便让人理解这是就需要使用到中缀表达式转后缀表达式中缀表达式转后缀表达式
后缀表达式适合计算式进行运算,但是人却不太容易写出来,尤其是表达式很长的情况下,因此在开发中,我们需要将中缀表达式转成后缀表达式。
具体步骤如下:示例: 1+((2+3)*4)-5
所对应的后缀表达式为 1 2 3 + 4 * + 5 -
将中缀表达式转换到list当中
public static ListTransformation(String s) { List ls = new ArrayList (); int i = 0;// 索引,用于遍历中缀表达式字符串 String str;// 多位数的拼接 char c; // 每遍历一个字符就将其放入到c中 do { // 如果c是一个非数字,加入到ls if ((c = s.charAt(i)) < 48 || ((c = s.charAt(i)) > 57)) { ls.add(c + ""); i++; } else { // 考虑多位数 str = ""; //当现在的这个索引还没有遍历到最后,以及这个字符是一个数字。 while (i < s.length() && ((c = s.charAt(i)) >= 48 && ((c = s.charAt(i)) <= 57))) { str += c; i++; } ls.add(str); } } while (i < s.length()); return ls;}
定义一个Operration类,定义一个方法用于返回运算符优先级
class Operration { private final static int ADD = 1; private final static int SUB = 1; private final static int MUL = 2; private final static int DIV = 2; // 使用对应方法,返回对应的优先级 public static int getValue(String oper) { int res = 0; switch (oper) { case "+": res = ADD; break; case "-": res = SUB; break; case "*": res = MUL; break; case "/": res = DIV; break; default: System.out.println("符号有误"); break; } return res; }}
对转换过来的后缀表达式进行运算处理
public static ListTransformationList(List ls) { // 初始化栈 Stack s1 = new Stack (); // s2这个栈没有出栈操作,使用ArrayList代替。 List s2 = new ArrayList (); // 遍历ls for (String item : ls) { // 是一个数入s2栈 if (item.matches("\\d+")) { s2.add(item); } else if (item.equals("(")) { s1.push(item); } else if (item.equals(")")) { // 右括号,则依次弹出s1栈顶的运算符,并压入s2,直到遇到左括号为止,此时将这一对括号丢弃 while (!s1.peek().equals("(")) { // 当没有找到对应的左括号,一直将数据弹出添加 s2.add(s1.pop()); } s1.pop(); // 将左括号弹出消除 } else { // 当 item 的优先级小于等于栈顶符号的优先级 while (s1.size() != 0 && Operration.getValue(s1.peek()) >= Operration.getValue(item)) { s2.add(s1.pop()); } //将item压入回s1栈 s1.push(item); } } //把s1中的剩下的运算符全部加入到s2中 while (s1.size()!=0) { s2.add(s1.pop()); } return s2;}
最后再定义一个中缀表达式进行测试
转载地址:http://xemzi.baihongyu.com/