Java堆栈的应用,进制的转换
堆栈的应用
栈的特点: 后进先出
进制转换
package com.bjpowernode.stack; /** * 使用栈完成进制转换 * @author 北京动力节点老崔 */ public class TestBaseConversion { public static void main(String[] args) { // System.out.println( convert(100, 2)); System.out.println( convert(100, 8)); // System.out.println( convert(100, 16)); } /** * 把一个十进制整数 num转换为decimal指定的进制 * @param num 接收十进制整数 * @param decimal 指定进制 * @return 返回num这个整数对应 的decimal进制的字符串 */ public static String convert(int num, int decimal) { MyArrayStack stack = new MyArrayStack(); //保存余数 int remainder = num % decimal ; //余数 while( num != 0 ) { stack.push( remainder ); //余数压栈 num = num / decimal; remainder = num % decimal ; } //出栈,余数倒序 StringBuilder sb = new StringBuilder(); while( !stack.isEmpty() ) { sb.append( stack.pop() ); } return sb.toString(); } }复制代码
检测表达式中括弧是否匹配
假设表达式中包含三种括弧: 小括弧(), 中括弧[], 大括弧{}, 这三种括弧可以任意嵌套;
(3+5) * [ 3-6] -{23/4}+([{}])
对于任意一个左括弧都需要有一个相应 的右括弧匹配, 最早出现的右括弧应该与最早出现的左括弧匹配. 符合栈的特点。
算法:
• 读取整个表达式, 如果是左括弧就直接入栈,等待与它对应的右括弧出现;
• 如果是右括弧, 则与当前栈顶的左括弧判断是否匹配
• 如果不匹配,说明表达式不合法
• 如果是右括弧, 栈已空, 表示不合法
• 读完整个表达式, 堆栈不空, 表示有左括弧没匹配上, 表达式不合法; 读完整个表达式,栈是空的表示所有括弧都能匹配。
package com.bjpowernode.stack; /** * 检测表达式中的括弧是否匹配 * @author 北京动力节点老崔 */ public class TestBracketMatch { public static void main(String[] args) { // System.out.println( bracketMatch("([{}])")); System.out.println( bracketMatch("([{(}])")); System.out.println( bracketMatch("([{}]))")); } //检测expression表达式 中的括弧是否匹配 public static boolean bracketMatch(String expression) { MyArrayStack stack = new MyArrayStack() ; //保存左括弧 //遍历整个表达式, 如果是左括弧就入栈, 如果是右括弧,就出栈进行判断是否匹配 for( int i = 0 ; i < expression.length(); i++) { //取出表达式的每个字符 char cc = expression.charAt(i); switch (cc) { case '(': case '[': case '{': stack.push(cc); //左括弧入栈, Java可以自动装箱与拆箱 break; case '}': if ( !stack.isEmpty() && stack.pop().equals('{')) { break; }else { return false; } case ']': if ( !stack.isEmpty() && stack.pop().equals('[')) { break; }else { return false; } case ')': if ( !stack.isEmpty() && stack.pop().equals('(')) { break; }else { return false; } } } //表达式遍历完后,如果栈是空的,表示括弧匹配, if (stack.isEmpty()) { return true; }else { return false; } } }复制代码
算术表达式的求值
1、四则运算的规则 :
先乘除后加减
先括弧内再括弧外
从左到右进行运算
2、表达式:
4 + 3 + ( 6 - 10 + 2*3) * 4
7 + ( 6 - 10 + 2*3) * 4
7 + ( -4 + 2*3) * 4
7 + ( -4 + 6) * 4
7 + 2 * 4
7 + 8
15
3、算法思路:
① 定义两个栈, 一个存储操作符operator, 一个存储操作数operand
② 读取表达式, 如果是操作数就存储到operand操作数栈
如果是操作符
• 操作符栈是空, 直接入栈
• 把操作符栈中的栈顶操作符与当前操作符进行优先级比较;
当前操作符优先级高, 操作符入栈;
当前操作符优先级低(栈顶操作符优先级高), 弹出栈顶操作符,从操作数栈中弹出两个操作数进行运算, 把运算结果存储到操作数栈中, 继续判断当前操作符与栈顶操作符的优先级。
③ 遍历完整个表达式, 两个栈都不为空, 依次弹出操作符opertor栈中的运算符与操作数栈中的两个操作数进行计算 , 把结果再存储到操作数栈中。
④ 如果操作符栈不为空, 或者操作数栈中的数不止有一个, 则表达式错误。
package com.bjpowernode.stack; /** * 使用栈计算算术表达式的值 * @author 北京动力节点老崔 */ public class TestCalculateExpression { public static void main(String[] args) { // String expression = "4+3+(6-10+2*3)*4"; double result = calculate( expression ); System.out.println( result ); } //定义方法计算 指定表达式的值 : 6834+3+(6-10+2*3)*43 private static double calculate(String expression) { MyArrayStack operatorStack = new MyArrayStack(); //存储操作符 MyArrayStack operandStack = new MyArrayStack(); //存储操作数 //遍历表达式中的操作数与操作符 for( int i = 0 ; i < expression.length() ; i++ ) { char cc = expression.charAt(i); //如果cc是数字 if ( Character.isDigit(cc)) { //取出操作数 StringBuilder sb = new StringBuilder(); //只要是数字就是操作数的一部分 while( Character.isDigit(cc)) { sb.append(cc); //6 i++; //取下个字符 if ( i >= expression.length() ) { //表达式结束 break; } cc = expression.charAt(i); //取下个字符 } //操作数入栈 operandStack.push(sb.toString()); //修正i变量的值 i--; // System.out.println( sb ); }else { //如果是操作符 //4+3+(6-10+2*3)*4 //1)栈为空, 直接把操作符入栈 if (operatorStack.isEmpty()) { operatorStack.push(cc); continue; } //2)操作符栈不为空的情况 while( !operatorStack.isEmpty()) { char op1 = (char) operatorStack.peek(); //判断栈中运算符与当前运算符的优先级 if ( compareOperator(op1, cc) < 0 ) { //当前运算符的优先级高于栈顶运算符的优先级 operatorStack.push(cc); break; }else if ( compareOperator(op1, cc) == 0) { //当前运算符的优先级等于 栈顶运算符的优先级, 只有一种 情况, 左一半小括弧遇到右一半小括弧的情况 operatorStack.pop() ; //栈中左一半小括弧出栈 break; }else { //栈顶运算符优先级高 //取出两个操作数 if (operandStack.isEmpty()) { throw new RuntimeException("表达式错误"); } double num1 = Double.parseDouble(operandStack.pop().toString()); if (operandStack.isEmpty()) { throw new RuntimeException("表达式错误"); } double num2 = Double.parseDouble(operandStack.pop().toString()); //取栈顶运算符 char operator = (char) operatorStack.pop(); //计算 num2 op num1 double result = compute(operator , num2, num1 ); //把结果存储到操作数栈中 operandStack.push(result); //如果当前操作符栈为空, 新的操作符入栈 if ( operatorStack.isEmpty()) { operatorStack.push(cc); break; } } } } } //当表达式 遍历完后, 如果操作符栈不为空, 需要继续计算 while( !operatorStack.isEmpty()) { char operator = (char) operatorStack.pop(); //如果操作数栈为空, 表达式错误 if (operandStack.isEmpty()) { throw new RuntimeException("表达式错误"); } double num1 = Double.parseDouble(operandStack.pop().toString()); if (operandStack.isEmpty()) { throw new RuntimeException("表达式错误"); } double num2 = Double.parseDouble(operandStack.pop().toString()); double result = compute(operator , num2, num1 ); operandStack.push(result); } //当操作符栈为空, 操作数栈中多于一个数, 表达式错误 if ( operandStack.getSize() > 1) { throw new RuntimeException("表达式错误"); } return Double.parseDouble(operandStack.pop().toString()); } //计算 num1 op num2 表达式的值 private static double compute(char operator, double num1, double num2) { switch (operator) { case '+': return num1 + num2; case '-': return num1 - num2; case '*': return num1 * num2; case '/': return num1 / num2; } return 0; } //判断两个运算符的优先级 ,如果op1优先级高返回正数, op2优先级高返回负数 private static int compareOperator(char op1, char op2) { if ( op1 == '+' || op1 == '-') { if (op2 == '*' || op2 =='/' || op2 =='(') { //第一个运算符是 +-, 第二个运算符是 * / ( return -1; } } if (op1 =='*' || op1 =='/') { if ( op2 =='(') { //第一个是*/, 第二个是( return -1; } } if ( op1 == '(') { if (op2 == ')') { return 0; }else { return -1; } } return 1; } }
伪原创工具 SEO网站优化 https://www.237it.com/
作者:不高兴就喝水叭
链接:https://juejin.cn/post/7035159287357767717