说明
- 调用之前写好的Calculator类，可以将中缀表达式转成后缀表达式。（改下方法权限就能调用了）
<mark>后缀表达式求值、中缀转后缀:</mark>https://blog.csdn.net/LawssssCat/article/details/102962279
<mark>写好的Calculator类</mark>https://blog.csdn.net/LawssssCat/article/details/102989450 - 代码中 parseSufixExpressionToBinaryTreeNodeTree()方法为"<mark>后缀表达式录入成表达式树</mark>"的实现。实现思路跟后缀求值一样。
代码
自定义的内部静态TreeNode类
private static class BinaryTreeNode<T> {
private T elementDate ;
private BinaryTreeNode<T> left ;
private BinaryTreeNode<T> right ;
public BinaryTreeNode(T e , BinaryTreeNode<T> left , BinaryTreeNode<T> 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<ind ;i++) {
System.out.print(" \\ ");
}
System.out.println(" "+this.elementDate);
//先打印左节点值
//后打印有节点值
if(this.left!= null && this.right != null) {
left.listAll(ind+1);
right.listAll(ind+1);
}
}
/* 后缀表达式形式打印 */
public void listAsExpression() {
if(this.left==null && this.right==null) {
System.out.print(this.elementDate);
}else {//
this.left.listAsExpression();
System.out.print(" ");
this.right.listAsExpression();
System.out.print(" "+this.elementDate);
}
}
}
实现类
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<String> lastNode ;
public static void parseSufixExpressionToBinaryTreeNodeTree(List<String> expression) {
Stack<BinaryTreeNode<String>> stackNumberNode = new Stack<>();
//遍历后缀表达式的每个字符
for(String s : expression) {
//如果是数字，进栈
if(!s.matches("\\D")) {
stackNumberNode.push(new BinaryTreeNode<String>(s, null, null));
}else {//如果不是数字
BinaryTreeNode<String> nodeRight = stackNumberNode.pop() ;
BinaryTreeNode<String> nodeLeft = stackNumberNode.pop() ;
BinaryTreeNode<String> operation =
new BinaryTreeNode<String>(s, nodeLeft, nodeRight);
stackNumberNode.push(operation);
}
}
lastNode = stackNumberNode.pop();
}
public BinaryTreeNode<String> getRoot(){
return lastNode;
}
}
测试方法
@Test
public void test01() {
/* * 准备 */
//中缀表达式
String expression = "1 + 7 * ( 8 + ( 16 + 12 ) / ( 13 - ( 20 / 15 ) ) )" ;
//后缀表达式
List<String> 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<String> 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<String> lastNode ;
public static void parseSufixExpressionToBinaryTreeNodeTree(List<String> expression) {
Stack<BinaryTreeNode<String>> stackNumberNode = new Stack<>();
//遍历后缀表达式的每个字符
for(String s : expression) {
//如果是数字，进栈
if(!s.matches("\\D")) {
stackNumberNode.push(new BinaryTreeNode<String>(s, null, null));
}else {//如果不是数字
BinaryTreeNode<String> nodeRight = stackNumberNode.pop() ;
BinaryTreeNode<String> nodeLeft = stackNumberNode.pop() ;
BinaryTreeNode<String> operation =
new BinaryTreeNode<String>(s, nodeLeft, nodeRight);
stackNumberNode.push(operation);
}
}
lastNode = stackNumberNode.pop();
}
public BinaryTreeNode<String> getRoot(){
return lastNode;
}
private static class BinaryTreeNode<T> {
private T elementDate ;
private BinaryTreeNode<T> left ;
private BinaryTreeNode<T> right ;
public BinaryTreeNode(T e , BinaryTreeNode<T> left , BinaryTreeNode<T> 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<ind ;i++) {
System.out.print(" \\ ");
}
System.out.println(" "+this.elementDate);
//先打印左节点值
//后打印有节点值
if(this.left!= null && this.right != null) {
left.listAll(ind+1);
right.listAll(ind+1);
}
}
public void listAsExpression() {
if(this.left==null && this.right==null) {
System.out.print(this.elementDate);
}else {//
this.left.listAsExpression();
System.out.print(" ");
this.right.listAsExpression();
System.out.print(" "+this.elementDate);
}
}
}
}
京公网安备 11010502036488号