本文共 4297 字，大约阅读时间需要 14 分钟。

说明

1. 调用之前写好的Calculator类，可以将中缀表达式转成后缀表达式。（改下方法权限就能调用了）
   后缀表达式求值、中缀转后缀:
   写好的Calculator类
2. 代码中$parseSufixExpressionToBinaryTreeNodeTree()$方法为"后缀表达式录入成表达式树"的实现。实现思路跟后缀求值一样。

代码

自定义的内部静态TreeNode类

private static class BinaryTreeNode
   
     {
   		private T elementDate ; 		private BinaryTreeNode
    
      left ; 		private BinaryTreeNode
     
       right ;		public BinaryTreeNode(T e , BinaryTreeNode
      
        left , BinaryTreeNode
       
         right ) {
   			this.elementDate = e; 			this.left = left ; 			this.right = right;		}				public void listAll() {
   			listAll(0); 		}		/*		 * 方便打印树形结构		 */		private void listAll(int ind) {
   			//打印本节点值			for(int i=0 ; i
       
      
     
    
   

实现类

package cn.edut.tree;import java.util.List;import java.util.Stack;import org.junit.Test;import cn.edut.clac.Calculator;public class ExpressionTree {
   		private static BinaryTreeNode
   
     lastNode ; 		public static  void parseSufixExpressionToBinaryTreeNodeTree(List
    
      expression) {
   		Stack
     
      
       > stackNumberNode = new Stack<>(); 		//遍历后缀表达式的每个字符		for(String s : expression) {
   			//如果是数字，进栈			if(!s.matches("\\D")) {
   				stackNumberNode.push(new BinaryTreeNode
       
        (s, null, null));			}else {
   //如果不是数字				BinaryTreeNode
        
          nodeRight = stackNumberNode.pop() ; BinaryTreeNode
         
           nodeLeft = stackNumberNode.pop() ; BinaryTreeNode
          
            operation = new BinaryTreeNode
           
            (s, nodeLeft, nodeRight); stackNumberNode.push(operation); } } lastNode = stackNumberNode.pop(); } public BinaryTreeNode
            
              getRoot(){ return lastNode; }}
            
           
          
         
        
       
      
     
    
   

测试方法

@Test	public void test01() {
   		/*		 * 准备 		 */		//中缀表达式		String expression = "1  + 7 * ( 8 + ( 16 + 12 ) / ( 13 - ( 20 / 15 ) ) )" ;		//后缀表达式		List
   
     sufixExpression = Calculator.parseSufixExpression(				Calculator.parseExpression(expression));		//计算结果		int result = Calculator.calcExpression(expression) ;		//打印		System.out.println("中缀表达式："+expression);		System.out.println("后缀表达式："+ sufixExpression.toString());		System.out.println("计算结果："+result);		/*		 * 准备完毕			 */				//分析表达式		parseSufixExpressionToBinaryTreeNodeTree(sufixExpression);		System.out.print("树以后缀摆列：");getRoot().listAsExpression();		System.out.println("\n树形式展示：(左上右下)");		getRoot().listAll();					}
   

测试结果

完整代码

package cn.edut.tree;import java.util.List;import java.util.Stack;import org.junit.Test;import cn.edut.clac.Calculator;public class ExpressionTree {
   	@Test	public void test01() {
   		/*		 * 准备 		 */		//中缀表达式		String expression = "1  + 7 * ( 8 + ( 16 + 12 ) / ( 13 - ( 20 / 15 ) ) )" ;		//后缀表达式		List
   
     sufixExpression = Calculator.parseSufixExpression(				Calculator.parseExpression(expression));		//计算结果		int result = Calculator.calcExpression(expression) ;		//打印		System.out.println("中缀表达式："+expression);		System.out.println("后缀表达式："+ sufixExpression.toString());		System.out.println("计算结果："+result);		/*		 * 准备完毕			 */				//分析表达式		parseSufixExpressionToBinaryTreeNodeTree(sufixExpression);		System.out.print("树以后缀摆列：");getRoot().listAsExpression();		System.out.println("\n树形式展示：(左上右下)");		getRoot().listAll();					}		private static BinaryTreeNode
    
      lastNode ; 		public static  void parseSufixExpressionToBinaryTreeNodeTree(List
     
       expression) {
   		Stack
      
       
        > stackNumberNode = new Stack<>(); 		//遍历后缀表达式的每个字符		for(String s : expression) {
   			//如果是数字，进栈			if(!s.matches("\\D")) {
   				stackNumberNode.push(new BinaryTreeNode
        
         (s, null, null)); }else { //如果不是数字 BinaryTreeNode
         
           nodeRight = stackNumberNode.pop() ; BinaryTreeNode
          
            nodeLeft = stackNumberNode.pop() ; BinaryTreeNode
           
             operation = new BinaryTreeNode
            
             (s, nodeLeft, nodeRight); stackNumberNode.push(operation); } } lastNode = stackNumberNode.pop(); } public BinaryTreeNode
             
               getRoot(){ return lastNode; } private static class BinaryTreeNode
              
                { private T elementDate ; private BinaryTreeNode
               
                 left ; private BinaryTreeNode
                
                  right ; public BinaryTreeNode(T e , BinaryTreeNode
                 
                   left , BinaryTreeNode
                  
                    right ) { this.elementDate = e; this.left = left ; this.right = right; } public void listAll() { listAll(0); } private void listAll(int ind) { //打印本节点值 for(int i=0 ; i
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     
    
   

转载地址：https://lawsssscat.blog.csdn.net/article/details/103011259 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！