Data structure stack

Article directory

Introduction to stack

Stack is an orderly list of first in first out (FILO). The first data is placed at the bottom of the stack, the last element is placed at the top of the stack, the last element is deleted first, and the first one is deleted first.

Stack implementation

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

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

    public boolean isEmpty(){
        return top==0;
    }

    public boolean push(int value){
        if(isFull()) return false;
        this.stack[top]=value;
        top++;
        return true;
    }

    public Integer pop(){
        if(isEmpty()) return null;
        int value=stack[top];
        top--;
        return value;
    }
}

Calculation of infix expression

Algorithmic thinking

For example, calculation: 3 + 2 * 6-2
The algorithm steps are as follows:
Maintain 2 stacks digital stack and symbol stack

  1. Scan from front to back, if you encounter numbers, directly enter the digital stack.
  2. If symbols are encountered, they can be divided into the following three situations:
  • If the symbol stack is empty, push it directly into the stack.
  • If the symbol stack is not empty and the symbol priority is less than or equal to the top element of the stack, pop will perform two numerical operations, and then re stack the result.
  • If the symbol stack is not empty and the symbol priority is greater than the top element of the stack, the symbol is directly pushed into the stack

code implementation

Address of Niuke: https://www.nowcoder.com/questionterminal/7b18aa6b7cc14f8eaae6b8acdeb890b? Tocommentid = 103161

import java.util.Scanner;
import java.util.Stack;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner cin = new Scanner(System.in);
        Main m=new Main();
        while (cin.hasNext()){
            String exp=cin.next();
            float res=m.nifix(exp);
            System.out.println((int)res);
        }

    }
    public float nifix(String expression){
        Stack<Float> numberStack=new Stack<>();
        Stack<Character> symbolStack=new Stack<>();
        String digit="";
        for(int i=0;i<expression.length();i++){
            char x=expression.charAt(i);
            if(Character.isDigit(x)){
                digit+=String.valueOf(x);
                if(i+1>=expression.length()||!Character.isDigit(expression.charAt(i+1))){
                    numberStack.push(Float.parseFloat(digit));
                    digit="";
                }

            }else {
                while (!symbolStack.isEmpty()&&priority(symbolStack.peek())>=priority(x)){
                    char y=symbolStack.pop();
                    float res=calRes(y,numberStack.pop(),numberStack.pop());
                    numberStack.push(res);
                }
                symbolStack.push(x);
            }
        }
        while (!symbolStack.isEmpty()){
            char y=symbolStack.pop();
            float res=calRes(y,numberStack.pop(),numberStack.pop());
            numberStack.push(res);
        }
        return numberStack.pop();
    }
    //Determine the priority of symbols
    private int priority(char x){
        if(x =='+'|| x =='-'){
            return 1;
        }else{
            return 2;
        }

    }
    //Calculation results
    private float calRes(char x,float num1,float num2){
        float res=0;
        switch (x){
            case '+':
                res=num1+num2;
                break;
            case '-':
                res=num2-num1;
                break;
            case '*':
                res=num1*num2;
                break;
            case '/':
                res=num2/num1;
                break;
        }
        return res;

    }
}

Suffix expression evaluation

Algorithmic thinking

Example of suffix expression:
The suffix expression corresponding to (3+4)x5-6 is 34+5x6 -.
Computer processing suffix expression is very direct, maintenance of a stack can complete the calculation.

code implementation

import java.util.Scanner;
import java.util.Stack;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner cin = new Scanner(System.in);
        Main m=new Main();
        while (cin.hasNext()){
            String exp=cin.next();
            float res=m.postfix(exp);
            System.out.println((int)res);
        }

    }
    public float postfix(String expression){
        String[] expressionItem=expression.split(" ");
        Stack<Float> stack=new Stack<>();
        for(int i=0;i<expressionItem.length;i++){
            String item=expressionItem[i];
            if(isNumeric(item)){
                stack.push(Float.parseFloat(item));
            }else {
                stack.push(cal(item,stack.pop(),stack.pop()));
            }

        }
        return stack.pop();
    }
    private static boolean isNumeric(String str){
        for (int i = str.length();--i>=0;){
            if (!Character.isDigit(str.charAt(i))){
                return false;
            }
         }
        return true;
    }
    //Calculation results
    private float cal(String item,float num1,float num2){
        float res=0;
        if(item.equals("+")){
            res=num2+num1;
        }else if(item.equals("-")){
            res=num2-num1;
        }else if(item.equals("/")){
            res=num2/num1;
        }else if(item.equals("*")){
            res=num2*num1;
        }
        return res;

    }
}

Infix expression to suffix expression

Limit must be 1 digit
Input:
a+bc/d-a+f/b
Output:
abcd/+a-fb/+

Algorithmic thinking

  • Scan infix expressions from left to right
  • Add suffix expression when a number is encountered
  • When an operator is encountered:
    a. If '(', stack
    b. If it is') ', the operators in the stack will be added to the suffix expression in turn until' ('appears and' is deleted from the stack '('
    c. If it is an operator other than the bracket, when the priority is higher than the stack top operator other than '(', it will be directly pushed into the stack; otherwise, from the top of the stack, the operators with higher priority and equal priority than the currently processed operators will pop up in turn until a lower priority or a left bracket is encountered.

code implementation

import java.util.Scanner;
import java.util.Stack;

public class Main {
    public static void main(String[] args) throws Exception {

        Scanner cin = new Scanner(System.in);
        Main m = new Main();
        while (cin.hasNext()) {
            String exp = cin.next();
            String res = m.niToPost(exp);
            System.out.println(res);
        }
    }

    //Judge whether it is a number
    private static boolean isNumeric(char c) {
        if (c == '+' || c == '-' || c == '*' || c == '/' || c == '(' || c == ')')
            return false;
        return true;
    }

    public String niToPost(String expression) {
        char[] res = new char[expression.length()];
        int index = 0;
        Stack<Character> symbolStack = new Stack<>();
        for (int i = 0; i < expression.length(); i++) {
            char x = expression.charAt(i);
            if (isNumeric(x)) {
                res[index] = x;
                index++;
            } else if (x == '(') {
                symbolStack.push(x);
            } else if (x == ')') {
                while (symbolStack.peek() != '(') {
                    res[index] = symbolStack.pop();
                    index++;
                }
                symbolStack.pop();
            } else {
                while (!symbolStack.isEmpty() && symbolStack.peek() != '(' && priority(symbolStack.peek()) >= priority(x)) {
                    res[index] = symbolStack.pop();
                    index++;
                }
                symbolStack.push(x);
            }

        }
        while (!symbolStack.isEmpty()) {
            res[index] = symbolStack.pop();
            index++;
        }
        return String.valueOf(res);
    }

    //Determine the priority of symbols
    private int priority(char x) {

        if (x == '+' || x == '-') {
            return 1;
        } else if (x == '*' || x == '/') {
            return 2;
        }
        return 0;
    }
}

Published 38 original articles, won praise 1, visited 784
Private letter follow

Tags: Java less

Posted on Thu, 06 Feb 2020 05:19:51 -0800 by jmajeremy