java实现逆波兰表达式

一、概念介绍： 1.中缀表达式就是常见的运算表达式，如(3+4)×5-6，对于人们来说会习惯计算这种计算式，但是对于计算机来说就不好计算，尤其是涉及到小数，括号等情况。 2.后缀表达式又称逆波兰表达式,与前缀表达式相似，只是运算符位于操作数之后比如：34+5*6-

中缀转后缀表达式步骤： 具体举例： 将中缀表达式“1+((2+3)×4)-5” 转换为"1 2 3 + 4 × + 5 –" 二、代码实现： 1.首先给出一个中缀表达式字符串，需要将其先转换为后缀表达式在交给计算机计算结果。由于字符串遍历操作不方便，现将中缀表达式转换列表储存，后勤方便遍历操作。原始表达式为："10+(2+3)*5-6"

//将中缀表达式转为list public static List<String> tolist(String s) { List<String> ls=new ArrayList<String>(); int i=0; String str; //拼接字符串，因为可能有连续的数字代表多位数的情形 char c; do{ //如果非数字，直接加入list 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; }

结果：

中缀表达式=[10, +, (, 2, +, 3, ), *, 5, -, 6]

2.开始将中缀表达式list转化为后缀表达式，也是列表表示

//直接将中序表达式转换为后缀表达式 public static List<String> parseSuffixExpressionList(List<String> ls) { //定义数栈和符号栈 Stack<String> stack = new Stack<String>(); //定义数栈 //Stack<String> stackoper = new Stack<String>(); //定义符号栈,可以用ArrayList来操作，因为不用出栈操作 List<String> list =new ArrayList<String>(); for(String item:ls) { //如果是一个数字，直接入队列,正则表达式判断 if(item.matches("\\d+")){ list.add(item); }else if(item.equals("(")){ //如果是左括号就直接入栈 stack.push(item); }else if(item.equals(")")){//如果是右括号依次弹出s1的符号，直到遇到左括号为止，将弹出的都入list队列 while (!stack.peek().equals("(")){//stack.peek是取队头元素 list.add(stack.pop()); } stack.pop(); //遇到左括号是要将括号弹出，必有，消除小括号 }else{ //判断item运算符的优先级 while(stack.size()!=0 && Operation.getValue(stack.peek())>=Operation.getValue(item)){ list.add(stack.pop()); } //还需要将item入栈 stack.push(item); } } //将s1中剩余运算符依次加入s2中 while (stack.size()!=0){ list.add(stack.pop()); } return list; }

结果：可以看到已经将括号消除

后缀表达式=[10, 2, 3, +, 5, *, +, 6, -]

3.在计算之前做的处理工作处理运算符的优先级

//判断运算符优先级 class Operation{ public static int getValue(String op) { int result=0; switch (op){ case "+": result=1; break; case "-": result=1; break; case "*": result=2; break; case "/": result=2; break; } return result; } }

4.计算后缀表达式

//开始计算表达式的值 public static int calculate(List<String> ls) { //建栈 Stack<String> stack= new Stack<String>(); for(String item:ls) { //使用正则表达式取数字 if(item.matches("\\d+")){ //匹配多位数 stack.push(item); }else { //运算符则运算 int num2=Integer.parseInt(stack.pop()); //字符串转int int num1=Integer.parseInt(stack.pop()); int res; 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("运算符未知"); } stack.push(res+""); } } return Integer.parseInt(stack.pop()); } }

5.主函数测试

public static void main(String []args) { //定义逆波兰表达式 (3+4)*5-6 //将中缀表达式转为list再操作 //将对应的中缀表达式的值转换为后缀表达式对应的list String expression="10+(2+3)*5-6"; List<String> InfixExpression = tolist(expression); System.out.println("中缀表达式="+InfixExpression); List<String> parseSuffixExpressionList=parseSuffixExpressionList(InfixExpression); System.out.println("后缀表达式="+parseSuffixExpressionList); System.out.printf("表达式的值为%d",calculate(parseSuffixExpressionList)); }

结果：

中缀表达式=[10, +, (, 2, +, 3, ), *, 5, -, 6] 后缀表达式=[10, 2, 3, +, 5, *, +, 6, -] 表达式的值为29

完整代码

package com.stack.implement; import java.util.ArrayList; import java.util.List; import java.util.Stack; /** * @author ymm * @create 2020-10-06 21:40 * 逆波兰表达式求值 * 040为止 */ public class Calculator { public static void main(String []args) { //定义逆波兰表达式 (3+4)*5-6 //将中缀表达式转为list再操作 //将对应的中缀表达式的值转换为后缀表达式对应的list String expression="10+(2+3)*5-6"; List<String> InfixExpression = tolist(expression); System.out.println("中缀表达式="+InfixExpression); List<String> parseSuffixExpressionList=parseSuffixExpressionList(InfixExpression); System.out.println("后缀表达式="+parseSuffixExpressionList); System.out.printf("表达式的值为%d",calculate(parseSuffixExpressionList)); } //将中缀表达式转为list public static List<String> tolist(String s) { List<String> ls=new ArrayList<String>(); int i=0; String str; char c; do{ //如果非数字 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; } //直接将中序表达式转换为后缀表达式 public static List<String> parseSuffixExpressionList(List<String> ls) { //定义数栈和符号栈 Stack<String> stack = new Stack<String>(); //定义数栈 //Stack<String> stackoper = new Stack<String>(); //定义符号栈,可以用ArrayList来操作，因为不用出栈操作 List<String> list =new ArrayList<String>(); for(String item:ls) { //如果是一个数字，直接入队列,正则表达式判断 if(item.matches("\\d+")){ list.add(item); }else if(item.equals("(")){ //如果是左括号就直接入栈 stack.push(item); }else if(item.equals(")")){//如果是右括号依次弹出s1的符号，直到遇到左括号为止，将弹出的都入list队列 while (!stack.peek().equals("(")){//stack.peek是取队头元素 list.add(stack.pop()); } stack.pop(); //遇到左括号是要将括号弹出，必有，消除小括号 }else{ //判断item运算符的优先级 while(stack.size()!=0 && Operation.getValue(stack.peek())>=Operation.getValue(item)){ list.add(stack.pop()); } //还需要将item入栈 stack.push(item); } } //将s1中剩余运算符依次加入s2中 while (stack.size()!=0){ list.add(stack.pop()); } return list; } //将数据转为arraylist中,数据处理 public static List<String> getliststring(String suffixExpression) { //将字符串分割 String[] split=suffixExpression.split(" "); List<String> list=new ArrayList<String >(); for(String ele:split){ list.add(ele); } return list; } //开始计算表达式的值 public static int calculate(List<String> ls) { //建栈 Stack<String> stack= new Stack<String>(); for(String item:ls) { //使用正则表达式取数字 if(item.matches("\\d+")){ //匹配多位数 stack.push(item); }else { //运算符则运算 int num2=Integer.parseInt(stack.pop()); //字符串转int int num1=Integer.parseInt(stack.pop()); int res; 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("运算符未知"); } stack.push(res+""); } } return Integer.parseInt(stack.pop()); } } //判断运算符优先级 class Operation{ public static int getValue(String op) { int result=0; switch (op){ case "+": result=1; break; case "-": result=1; break; case "*": result=2; break; case "/": result=2; break; } return result; } }

B站java数据结构