栈和递归2--栈的应用

栈的应用

括号匹配问题

问题：

给出一个字符串，里面有三类括号：“（，）”、 “[，]”、 ”{，}"

括号成队出现并且嵌套正确，返回true ；否则返回false；

示例：

input：“({()})"

output: true

input:"{(]}"

output: false

算法：

依次扫描字符串。

1、如果出现左括号【 ‘(’、‘[’ 、‘{’ 】时。进栈。

2、如果出现右括号【 ‘)’、‘]’ 、‘}’ 】时

​ 2.1、若栈空，表达式不匹配

​ 2.2、若栈非空，取出栈顶元素，如果匹配则栈顶元素出栈，如果不匹配，表达式不匹配，直接退出 扫描。

3、最后还需要判断栈是否空，若空，则匹配成功

示例：表达式 “ ([]{}) ” 是否匹配成功。

1、第一次扫描：’（ ‘ 左括号进栈

2、第二次扫描： ‘ [ '左括号进栈

3、第三次扫描：’ ] ’ 右括号，当前栈非空，取出栈顶元素， ‘ [ ’ ,匹配成功 ，栈顶元素出栈。

4、第四次扫描：’ { ‘ 左括号进栈

5、第五次扫描：’ } ’ 右括号，当前栈非空，取出栈顶元素， ‘ { ’ ,匹配成功 ，栈顶元素出栈。

6、第六次扫描：’ ) ’ 右括号，当前栈非空，取出栈顶元素， ‘ ) ’ ,匹配成功 ，栈顶元素出栈。

7、栈为空，匹配成功。

代码实现：

/**
 *
 * @param par  字符串表达式
 * @return   是否匹配成功
 */
public static Boolean parenthseis(String par){
    //先将字符串转换成字符数组
    char[] chars = par.toCharArray();

    Boolean flag = true;
    //定义一个字符栈
    Stack<Character> stack = new Stack<>();

    //开始扫描
    for (int i = 0; i < chars.length; i++) {
        //如果栈空且扫描到右括号
        if(stack.isEmpty() && (chars[i] == '}' || chars[i] == ']' || chars[i] == ')')){
            flag = false;
            break;
        }
        //如果扫描到左括号
        if((chars[i] == '{' || chars[i] == '[' || chars[i] == '(')){
            stack.push(chars[i]);
        }
        //如果栈非空，且扫描到右括号
        if(!stack.isEmpty() && (chars[i] == '}' || chars[i] == ']' || chars[i] == ')')){
            //取出栈顶元素，这里可以直接取出，如果不匹配，就直接退出循环了。不用担心数据丢失
            char pop = stack.pop();

            if(pop == '(' && chars[i] != ')' ){
                flag = false;
                break;
            }

            if(pop == '[' && chars[i] != ']'){
                flag = false;
                break;
            }

            if(pop == '{' && chars[i] != '}'){
                flag = false;
                break;
            }
        }
    }

    //如果栈非空，表达式不匹配
    if(stack.size() != 0){
        flag = false;
    }

    return flag;
}

测试：

public static void main(String[] args) {
        System.out.println(parenthseis("({})"));   //true
        System.out.println(parenthseis("({[})"));  //false
        System.out.println(parenthseis(""));       //true
        System.out.println(parenthseis(")({})"));  //false
}

进制转换

问题：将十进制转换成二进制和十六进制

示例：

二进制：

input ：8

output : 1000

十六进制：

input : 16

output : 10

算法：

十进制转换成二进制：除以2取余，倒序排列。使用栈就是为了倒序排列

十进制转换成十六进制：除以16取余，当余数为10-15时，就用 a-f来表示，最后倒序排列

示例：将42转换成二进制

出栈：二进制为：101010

示例：将30转换成十六进制

出栈：十六进制为 1e

代码实现：

/**
 * 十进制转换成二进制
 * @param num  十进制数字
 * @return  二进制字符串
 */
public static String Binary(int num){

    if(num<0){
        throw new RuntimeException("数字必须为正整数");
    }

    //定义栈
    Stack<Integer> arrayStack = new Stack<Integer>();

    //开始循环
    while( num != 0){
        //将余数进栈
        arrayStack.push(num % 2);
        num = num / 2;
    }

    //定义字符序列可变的字符串
    StringBuilder stringBuilder = new StringBuilder();

    while(arrayStack.size() != 0){
        //出栈
        stringBuilder.append(arrayStack.pop());
    }

    return stringBuilder.toString();

}


/**
 * 十进制转十六进制
 * @param num  十进制数字
 * @return   十六进制字符串
 */
public static String Hexadecimal(int num){
    if(num<0){
        throw new RuntimeException("数字必须为正整数");
    }

    Stack<String> stack = new Stack<>();

    while(num != 0){

        switch (num % 16){
            case 10: stack.push("a");
                break;
            case 11: stack.push("b");
                break;
            case 12: stack.push("c");
                break;
            case 13: stack.push("d");
                break;
            case 14: stack.push("e");
                break;
            case 15: stack.push("f");
                break;
                //如果余数是 0 - 9 ，将数字转换成字符串，压入栈
            default:stack.push(Integer.toString(num % 16));
                break;
        }

        num /= 16;
    }

    StringBuilder stringBuilder = new StringBuilder();
    while(stack.size() != 0){
        stringBuilder.append(stack.pop());
    }

    return stringBuilder.toString();
}

测试：

public static void main(String[] args) {
    System.out.println(Binary(42));    //101010
    System.out.println(Hexadecimal(30));  //1e
    System.out.println(Binary(-1));  //java.lang.RuntimeException: 数字必须为正整数
}

简单的四则运算

示例：

代码实现：

/**
 * 计算
 * @param expression1  字符串表达式
 */
public static void calc(String expression1){
    char[] expression = expression1.toCharArray();
    //创建两个栈，一个存储数据，另一个存储运算符。
    Stack<Integer> numstack = new Stack<>();
    Stack<Character> operstack = new Stack<>();


    //定义相关变量
    int index = 0;  //用于扫描字符数组的下标
    char ch=' ';    //用于存储扫描结果
    int num1 = 0;   //用于计算
    int num2 = 0;   //用于计算
    char oper;      //符号
    int res = 0;    //计算结果


    //多位数拼接
    StringBuilder nums = new StringBuilder();

    //开始while循环
    while(true){
        //扫描
        ch = expression[index];
        //判断是否是运算符
        if(isOper(ch)){
            //如果是运算符栈非空
            if(!operstack.isEmpty()){
                //判断当前运算符和栈顶运算符的优先级
                //如果，栈顶的优先级高，则
                //      取出数据栈的两个元素，，，注意顺序！！！！！
                //      取出符号栈的一个元素，，然后计算
                if(priority(ch) <= priority(operstack.peek())){
                    //注意取出的顺序，涉及到运算
                    num1 = numstack.pop();
                    num2 = numstack.pop();

                    oper = operstack.pop();
                    //一个运算函数，数字和符号传入，注意顺序
                    res = cal(num1,num2,oper);
                    //然后将结构传入数据栈
                    numstack.push(res);
                    //当当前扫描的符号传入符号栈
                    operstack.push(ch);
                }else{    //如果当前的运算符优先级大于栈顶运算符，当前运算符进栈
                    operstack.push(ch);
                }
            }else{//如果运算符栈是空，这直接入栈
                operstack.push(ch);
            }
        }
        //如果扫描到数字
        else{
            //将ch拼接到nums中
            nums.append(ch);
            //如果当前数字是最后一个，直接进栈
            if(index == expression.length - 1){
                numstack.push(Integer.parseInt(nums.toString()));
            }else {
                //如果数字不是最后一个
                //且下一个扫描到的是运算符
                if(isOper(expression[index+1])){
                    //直接进栈
                    numstack.push(Integer.parseInt(nums.toString()));
                    //将nums清空！！
                    nums.delete(0,nums.length());
                }
                //如果扫描到的下一个是数字，则在下一次循环中拼接到nums中，直到出现运算符
            }

        }

        index++;
        if(index >= expression.length){
            break;
        }
    }

    //结束扫描后，如果符号栈为空，那么还需要运算，此时，符号栈中的符号不区分优先级了。
    while (true){
        if(operstack.isEmpty()){
            break;
        }
        //数据栈弹出两个元素
        num1 = numstack.pop();
        num2 = numstack.pop();
        //符号栈弹出元素
        oper = operstack.pop();
        //计算
        res = cal(num1,num2,oper);
        //将结果压入数据栈
        numstack.push(res);
    }


    System.out.println(numstack.pop());
}

/**
 * 判断是否是运算符
 * @param val  扫描的字符
 * @return  是否是运算符
 */
public static boolean isOper(char val){
    return val == '+' || val == '-' || val == '*' || val == '/';
}

/**
 * 计算
 * @param num1  数据1
 * @param num2  数据2
 * @param oper  符号
 * @return   返回计算结果
 */
public static int cal(int num1,int num2,int oper){
    int res = 0;
    switch (oper){
        case '+':
            res = num2 + num1;
            break;
        case '-':
            res = num2 - num1;
            break;
        case '*':
            res = num2 * num1;
            break;
        case '/':
            res = num2 / num1;
            break;

        default:
            break;
    }

    return res;
}

/**
 * 得到运算符优先级
 * @param oper  字符
 * @return 返回运算符优先级
 */
public static int priority(char oper){
    if(oper == '*' || oper == '/'){
        return 1;
    }
    else if(oper == '+' || oper == '-'){
        return 0;
    }
    else {
        return 0;
    }
}

测试：

public static void main(String[] args) {
    calc("4*5+18/3");  //26
    calc("4+6*9-20");  //38
}