环保公司网站模板,金华建站方案,可以个人开店的电商平台,网站开发记科目问题背景
1. 实现一个简单的计算器。通过键盘输入一个包含圆括号、加减乘除等符号组成的算术表达式字符串#xff0c;输出该算术表达式的值。要求#xff1a;
#xff08;1#xff09;系统至少能实现加、减、乘、除等运算#xff1b;
#xff08;2#xff09;利用二叉…问题背景
1. 实现一个简单的计算器。通过键盘输入一个包含圆括号、加减乘除等符号组成的算术表达式字符串输出该算术表达式的值。要求
1系统至少能实现加、减、乘、除等运算
2利用二叉树算法思想求解表达式的值先构造由表达式构成的二叉树按中序、后序遍历的方式输出二叉树中的结点然后再利用通过对二叉树进行后序遍历求解算术表达式的值。
思路描述
构建表达式二叉树先用栈将算术表达式转成后缀表达式具体思路参考再根据后缀表达式构建表达式二叉树构建过程从左到右扫描后缀表达式的每个元素如果当前元素是操作数则创建一个只包含该操作数的节点并将该节点压入栈中如果当前元素是操作符则创建一个只包含该操作符的节点并从栈中弹出两个节点作为其左右子节点再将该节点压入栈中。最后栈中唯一的节点即为根节点。表达式二叉树求值后序遍历二叉树递归计算左右子树的值代入运算符计算 代码实现
//二叉链表存储二叉树
public class TreeNode {String value;TreeNode left;TreeNode right;public TreeNode(String value){this.valuevalue;}public TreeNode(String value, TreeNode left, TreeNode right) {this.value value;this.left left;this.right right;}
}
public class Calculator {private TreeNode root;public Calculator() {root null;}public Calculator(TreeNode root) {this.root root;}//中缀转后缀List中每个元素就是后缀表达式中每个操作数或运算符public static ListString infixToPostfix(String infixExpression){StackCharacter operatorStacknew Stack();ListString postfixExpressionnew ArrayList();for(int i0;iinfixExpression.length();i){//如果是数字if(Character.isDigit(infixExpression.charAt(i))){//可能是多位的数StringBuilder tempnew StringBuilder();temp.append(infixExpression.charAt(i));while (iinfixExpression.length()Character.isDigit(infixExpression.charAt(i))){temp.append(infixExpression.charAt(i));}postfixExpression.add(temp.toString());i--;//while判断完后i多往后挪了一位所以要-1}//如果是左括号else if(infixExpression.charAt(i)(){operatorStack.push(infixExpression.charAt(i));}//如果是右括号去匹配左括号else if(infixExpression.charAt(i))){while (!operatorStack.empty()operatorStack.peek()!(){postfixExpression.add(operatorStack.pop());}operatorStack.pop();}//如果是-*/else {//将优先级当前运算符优先级的运算符pop出来追加到后缀表达式中while (!operatorStack.empty()getPrecedence(infixExpression.charAt(i))getPrecedence(operatorStack.peek())){postfixExpression.add(operatorStack.pop());}operatorStack.push(infixExpression.charAt(i));}}//将栈中剩余的运算符依次pop出来追加到结果中while (!operatorStack.empty()){postfixExpression.add(operatorStack.pop());}return postfixExpression;}//在中缀转后缀时要判断符号优先级private static int getPrecedence(char operator) {switch (operator) {case :case -:return 1;case *:case /:case %:return 2;default:return 0;}}//利用后缀表达式构建表达式二叉树public static TreeNode buildExpressionTree(ListString postfixExpression){StackTreeNode stacknew Stack();//从左至右遍历后缀表达式for(String str:postfixExpression){//如果是运算数if(str.charAt(0)48str.charAt(0)57){TreeNode treeNode new TreeNode(str, null, null);stack.push(treeNode);} else {//如果是运算符//从栈中弹出两个节点TreeNode pop1 stack.pop();TreeNode pop2 stack.pop();TreeNode treeNode new TreeNode(str, pop1, pop2);stack.push(treeNode);}}//最后栈中剩余的节点就是二叉树根节点return stack.peek();}//中序遍历表达式二叉树(左根右)public static void inorderTraversal(TreeNode treeNode){if(treeNodenull)return;inorderTraversal(treeNode.left);System.out.print(treeNode.value );inorderTraversal(treeNode.right);}//后序遍历表达式二叉树左右根public static void postorderTraversal(TreeNode treeNode){if(treeNodenull)return;postorderTraversal(treeNode.left);postorderTraversal(treeNode.right);System.out.print(treeNode.value );}//后序遍历表达式二叉树求值public int evaluateExpression(){return evaluateExpression(root);}public int evaluateExpression(TreeNode root){if(rootnull){return 0;}// 递归计算左右子树的值int leftValue evaluateExpression(root.left);int rightValue evaluateExpression(root.right);switch (root.value){case :return leftValuerightValue;case -:return leftValue-rightValue;case *:return leftValue*rightValue;case /:return leftValue/rightValue;default:// 如果是操作数则返回对应的整数值return Integer.valueOf(root.value);}}
} 运行效果
public class Main {public static void main(String[] args) {System.out.println(请输入你要计算的表达式);Scanner sc new Scanner(System.in);String infixExpression sc.next();ListString postfixExpression Calculator.infixToPostfix(infixExpression);//中缀转后缀TreeNode binaryTree Calculator.buildExpressionTree(postfixExpression);//利用后缀表达式构建表达式二叉树System.out.print(中序遍历);Calculator.inorderTraversal(binaryTree);//中序遍历System.out.println();System.out.print(后序遍历);Calculator.postorderTraversal(binaryTree);//后序遍历System.out.println();Calculator calculator new Calculator(binaryTree);int i calculator.evaluateExpression();System.out.println(值为i);}
}
