java中缀表达式转后缀表达式,前缀表达式java
00-1010中缀表示法java实现后缀表示法逆波兰表达式计算方法和中缀表示法转换java后缀表达式计算实现方法示例代码实现
00-1010观察一个常见的公式：3 4*5
当然，我们知道应该先算4*5，然后把这个结果加到3上得到最终结果。
如果是比较复杂的公式：3 4 *(5-6)/7 8)
这仍然不能打败我们。请记住()，优先级最高，然后是*/，最后是-。这是通常的中缀符号。
但是通过算法分析，这个表达式的运行时间应该是O(n ^ 2)，因为它每次都需要判断优先级。
当表达式很长很复杂时，就需要更适合计算机的算法。
目录
简介
逆波兰记法(RPN)是波兰数学家扬武卡谢维奇在1920年引入的一种数学表达式。在逆波兰记法中，所有运算符都放在操作数之后，因此也称为后缀记法。
波兰符号不需要括号来标识操作符的优先级。在波兰符号中，运算符放在操作数之后。
比如表达“三加四”的时候，把“3 4”写成“3 4”。如果有多个运算符，则运算符放在第二个操作数之后，所以常规中缀记法中的“3-4 5”在逆波兰记法中写成“3 4-5”:先3减4，再5。3354反向波兰符号的维基百科条目。
这种表示法有以下特点：
不需要括号。与中缀表达式不同，逆波兰表达式不需要遍历整个公式来寻找一对括号。波兰语逆表达式的实现一般是基于栈的。在计算机中，栈的数据结构是非常有效的。运行时间为O(N)。不满足交换规律。
中缀表示法java实现
例如2*3+4*5
可以这样算。2和3的和是5。保存这个数，然后计算4*5的值，保存，最后计算两个同时存在的值。是这样写的2 ^ 3 * 4 ^ 5 *。这是后缀或反向波兰符号。
堆栈实现的过程很简单，规则如下。
从头开始读。如果是一个数字，就读取它，然后将它压入堆栈。如果是符号，取栈顶的元素两次，通过符号计算，然后把得到的数压入栈中。
Java实现
public class prn calculator { public static double prn cal(String PRN){ stack double stack=new stack double()；string[]ss=prn . split( )；for(int I=0；i ss .长度；i ){ if(ss[i]。matches( d ))stack . push(double . value of(ss[I])；if(ss[i]。matches([- * /]){ double b=stack . pop()；double a=stack . pop()；if(ss[i]。equals())stack . push(a b)；if(ss[i]。equals(-))stack . push(a-b)；if(ss[i]。equals( *))stack . push(a * b)；if(ss[i]。equals(/))stack . push(a/b)；} }返回stack . pop()；} }测试类
public class prn test { public static void main(String[]args){ String s= 2 3 * 4 5 * ；双重结果
= PRNCalculator.PRNCal(s); System.out.println("输入的逆波兰表达式:" + s); System.out.println("计算结果:" + result); }}打印结果：
输入的逆波兰表达式:2 3 * 4 5 * +计算结果:26.0
与中缀记法的转换
和后缀表达式的计算方法类似，一个中缀记法转换到后缀记法，也可以利用堆栈来实现。
从头开始读取。如果读取到的是数字，将其输出。如果读取到的是符号，则判断该符号的优先级是否高于栈顶或栈为空，是，则压入栈中；否，则将栈顶输出并继续判断。如果读取到的是括号，(会直接被压入栈；在读取到)的时候，栈会一直弹出直到遇到(。下面是这个转换的Java实现。
package PRNCalculator;import java.util.Stack;public class PRNCalculator { public static String PRNTansf(String s){ Stack<String> stack = new Stack<String>(); String[] ss = s.split(" "); StringBuffer sb = new StringBuffer(); for(int i = 0; i < ss.length; i++){ if(ss[i].matches("\d")) sb.append(ss[i] + " "); if(ss[i].matches("[+-*/()]")) { if(stack.isEmpty()) { stack.push(ss[i]); } else { if(ss[i].matches("[+-]")) { while(!stack.isEmpty() && !stack.peek().matches("[(]")) sb.append(stack.pop()).append(" "); if(stack.isEmpty() stack.peek().matches("[(]")) stack.push(ss[i]); } if(ss[i].matches("[*/]")){ while(stack.peek().matches("[*/]") && !stack.peek().matches("[(]")) sb.append(stack.pop()).append(" "); if(stack.isEmpty() stack.peek().matches("[(]") stack.peek().matches("[+-]")) stack.push(ss[i]); } if(ss[i].matches("[(]")) { stack.push(ss[i]); } if(ss[i].matches("[)]")){ while(!stack.peek().matches("[(]")) sb.append(stack.pop()).append(" "); if(stack.peek().matches("[(]")) stack.pop(); } } } } while(!stack.isEmpty()) sb.append(stack.pop()).append(" "); return sb.toString(); }}* Test类*package PRNCalculator;public class PRNTest { public static void main(String[] args) { String s = "4 + 5 + 8 * ( 6 + 8 * 7 ) / 3 + 4"; String PRN = PRNCalculator.PRNTansf(s); System.out.println("输入的表达式为："); System.out.println(s); System.out.println("输出的逆波兰表达式为："); System.out.println(PRN); double result = PRNCalculator.PRNCal(PRN); System.out.println("该表达式计算结果为："); System.out.println(result); }}打印结果：
输入的表达式为：4 + 5 + 8 * ( 6 + 8 * 7 ) / 3 + 4输出的逆波兰表达式为：4 5 + 8 6 8 7 * + * 3 / + 4 +该表达式计算结果为：178.33333333333334
java后缀表达式的计算
实现方法
从左至右扫描表达式
遇到数字时，将数字压栈，遇到运算符时，弹出栈顶的两个数，计算并将结果入栈
重复2直到表达式最右端，最后运算得出的值即为表达式的结果
示例
计算后缀表达式的值：1 2 3 + 4 × + 5 -
从左至右扫描，将1，2，3压入栈；
遇到+运算符，3和2弹出，计算2+3的值，得到5，将5压入栈；
遇到4，将4压入栈
遇到×运算符，弹出4和5，计算5×4的值，得到20，将20压入栈；
遇到+运算符，弹出20和1，计算1+20的值，得到21，将21压入栈；
遇到5，将5压入栈；
遇到-运算符，弹出5和21，计算21-5的值，得到16为最终结果
代码实现
public class ReversePolishNotation { public static void main(String[] args) { String notation = "10 2 3 + 4 * + 5 -"; ReversePolishNotation reversePN = new ReversePolishNotation(); Stack<Integer> numStack = new Stack<>(); //以空格分隔上述表达式，存到数组中 String[] s = notation.split(" "); //遍历数组 for (int i = 0; i < s.length; i++) { if (!reversePN.isOperator(s[i])){ //如果不是运算符，则压栈 numStack.push(Integer.parseInt(s[i])); } else { //为运算符，则取出栈顶的两个数字进行运算 int result = reversePN.calculation(numStack.pop(), numStack.pop(), s[i]); //将结果压栈 numStack.push(result); } } //循环结束，栈中仅剩的一个元素及为结果 System.out.println(numStack.pop()); } //判断是否是运算符 public boolean isOperator(String oper){ return oper.equals("+") oper.equals("-") oper.equals("*") oper.equals("/") ; } //计算 public int calculation(int num1, int num2, String oper){ switch (oper){ case "+": return num2 + num1; case "-": return num2 - num1; case "*": return num2 * num1; case "/": return num2 / num1; default: return 0; } }}以上为个人经验，希望能给大家一个参考，也希望大家多多支持盛行IT。
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。