数据结构与算法-栈

栈相当于一个容器 ,有先进后出的特点 , 利用栈的特点可以通过逆波兰表达式(后缀表达式)来对数据表达式进行运算 , 计算难度低于前缀表达式 ;

栈

特点 : 先进后出

中缀表达式

与人的计算逻辑一致

//有瑕疵 , 大致实现中缀表达式的过程
/**
 * author:小刘
 * 日期: 2020/2/26 19:38
 */

public class ExpressionStackDemo {
    public static void main(String[] args) {
        String express = "9+2*5-1";
        Stack numStack = new Stack(10);
        Stack operStack = new Stack(10);
        //定义相关的变量
        int index = 0;
        int num1 = 0;
        int num2 = 0;
        int res = 0;
        int opr = 0;
        char ch = ' ';
        while (true) {
            ch = express.substring(index, index + 1).charAt(0);
            //判断字节是否为操作符
            if (operStack.isOpr(ch)) {
                //为符号栈不为空
                if (!operStack.isEmpty()) {
                    //如果当前字符的优先级小于栈顶的优先级,栈顶先弹出计算,然后在将当前操作符压入栈
                    if (operStack.priority(ch) <= operStack.priority(operStack.peek())) {
                        num1 = numStack.pop();
                        num2 = numStack.pop();
                        opr = operStack.pop();
                        res = numStack.cal(num1, num2, opr);
                        numStack.push(res);
                        operStack.push(ch);
                    } else {
                        operStack.push(ch);
                    }
                } else {
                    operStack.push(ch);
                }
            } else {
                numStack.push(ch-48 );
            }
            index++;
            if (index >= express.length()) {
                break;
            }
        }
		//将栈上的元素一次进行计算 , 最后数字栈里就是计算的结果
        while(true){
            if(operStack.isEmpty()){
                break;
            }
            num1 = numStack.pop();
            num2 = numStack.pop();
            opr = operStack.pop();
            res = numStack.cal(num1, num2, opr);
            numStack.push(res);
        }
        System.out.printf(express + "=%d", numStack.pop());
    }
}

class Stack {
    private int top = -1;
    private int maxSize;
    private int[] stack;

    public Stack(int maxSize) {
        this.maxSize = maxSize;
        stack = new int[this.maxSize];
    }

    public boolean isFull() {
        return top == maxSize - 1;
    }

    public boolean isEmpty() {
        return top == -1;
    }

    public void push(int number) {
        if (isFull()) {
            System.out.println("栈为满,添加失败....");
            return;
        }
        top++;
        stack[top] = number;
    }

    public int pop() {
        if (isEmpty()) {
            System.out.println("栈为空,移除失败....");
            return 0;
        }
        int value = stack[top];
        top--;
        return value;
    }

    public void show() {
        if (isEmpty()) {
            System.out.println("栈为空....");
            return;
        }
        for (int i = top; i >= 0; i--) {
            System.out.printf("stack[%d]为%d \n", i, stack[i]);
        }
    }

    //判断优先级
    public int priority(int opr) {
        if (opr == '*' || opr == '/') {
            return 1;
        } else if (opr == '+' || opr == '-') {
            return 0;
        } else {
            return -1;
        }
    }

    //判断表达式里面的那个字节是不是操作符号
    public boolean isOpr(char val) {
        return val == '+' || val == '-' || val == '*' || val == '/';
    }

    //查看栈顶数据
    public int peek() {
        return stack[top];
    }

    //计算
    public int cal(int num1, int num2, int opr) {
        int res = 0;
        switch (opr) {
            case '+':
                 res = (num1 + num2);
                 break;
            case '-':
                 res = (num2 - num1);
                 break;
            case '*':
                 res = (num2 * num1);
                 break;
            case '/':
                 res = (num2 / num1);
                 break;
        }
        return res;
    }
}

逆波兰表达式

import java.util.ArrayList;
import java.util.List;
/**
 * author:小刘
 * 日期: 2020/3/1 16:40
 */
public class SuffixExpressionStackDemo {
    public static void main(String[] args) {
        String expression = "1111+((122+300)*400)-5";
        List<String> list = parseExpressionToList(expression);
        List<String> suffixList = toSuffixExpression(list);
        System.out.printf("答案是%d", cal(suffixList));

    }

    public static List<String> toSuffixExpression(List<String> list) {
        Stack2 s1 = new Stack2(10); //容量为10的符号栈
        List<String> s2 = new ArrayList<>();
        for (String item : list) {
            //如果是数
            if (item.matches("\\d+")) {
                s2.add(item);
            } else if (item.equals("(")) {
                s1.push(item);
            } else if (item.equals(")")) {
                while (!s1.peek().equals("(")) {
                    s2.add(s1.pop());
                }
                s1.pop();//将 "(" 弹出
            } else {
                //是符号 ,判断当前的优先级是否小于栈顶, 如果是弹出,后在入栈
                while (!s1.isEmpty() && !s1.peek().equals("(") && Opertion.getValue(item) <= Opertion.getValue(s1.peek())) {
                    s2.add(s1.pop());
                }
                //入栈
                s1.push(item);
            }

        }
        //将剩余的符号加到s2
        while (!s1.isEmpty()) {
            s2.add(s1.pop());
        }
        return s2;
    }

    public static List<String> parseExpressionToList(String expression) {
        List<String> list = new ArrayList<>();
        int index = 0; // 指针用来索引字符串
        String str; //多位数进行拼接,这里不能使用空串,是为了后面复位
        char ch; //用来存储每次遍历的字符
        while (index < expression.length()) {
            if ((ch = expression.charAt(index)) < 48 || ((ch = expression.charAt(index)) > 57)) {
                //说明在ASCII这个范围内不是数字
                list.add(String.valueOf(ch));
                index++;
            } else {
                //是一个数字0-9
                str = "";
                while (index < expression.length() && ((ch = expression.charAt(index)) >= 48) && ((ch = expression.charAt(index)) <= 57)) {
                    str += ch;
                    index++;
                }
                list.add(str);
            }
        }
        return list;
    }

    //计算
    public static int cal(List<String> list) {
        Stack2 s2 = new Stack2(10);
        for (String item : list) {
            if (item.matches("\\d+")) {
                s2.push(item);
            } else {
                int res = 0;
                String pop1 = s2.pop();
                String pop2 = s2.pop();
                if (item.equals("+")) {
                    res = Integer.valueOf(pop2) + Integer.valueOf(pop1);
                    s2.push(String.valueOf(res));
                } else if (item.equals("-")) {
                    res = Integer.valueOf(pop2) - Integer.valueOf(pop1);
                    s2.push(String.valueOf(res));
                } else if (item.equals("*")) {
                    res = Integer.valueOf(pop2) * Integer.valueOf(pop1);
                    s2.push(String.valueOf(res));
                } else if (item.equals("/")) {
                    res = Integer.valueOf(pop2) / Integer.valueOf(pop1);
                    s2.push(String.valueOf(res));
                }

            }
        }
        return Integer.valueOf(s2.pop());
    }
}

class Stack2 {
    private int top = -1;
    private int maxSize;
    private String[] stack;

    public Stack2(int maxSize) {
        this.maxSize = maxSize;
        stack = new String[this.maxSize];
    }

    public boolean isFull() {
        return top == maxSize - 1;
    }

    public boolean isEmpty() {
        return top == -1;
    }

    public void push(String number) {
        if (isFull()) {
            System.out.println("栈为满,添加失败....");
            return;
        }
        top++;
        stack[top] = number;
    }

    public String pop() {
        if (isEmpty()) {
            System.out.println("栈为空,移除失败....");
            return "0";
        }
        String value = stack[top];
        top--;
        return value;
    }

    public void show() {
        if (isEmpty()) {
            System.out.println("栈为空....");
            return;
        }
        for (int i = top; i >= 0; i--) {
            System.out.printf("stack[%d]为%d \n", i, stack[i]);
        }
    }

    public String peek() {
        return stack[top];
    }
}

//获取符号的优先级
class Opertion {
    static final int Add = 1;
    static final int SUB = 1;
    static final int MUL = 2;
    static final int DEV = 2;

    public static int getValue(String operation) {
        int result = 0;
        switch (operation) {
            case "+":
                return result = Add;
            case "-":
                return result = SUB;
            case "*":
                return result = MUL;
            case "/":
                return result = DEV;
            default:
                throw new RuntimeException("运算符号有误");
        }
    }
}

赏

小劉感谢您的赞赏

微信