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;
}
}
