پشته (Stack) در برنامه نویسی

function push(e: E){
  linkedList.addLast(e);
}
        

function pop(): E{
  return linkedList.removeLast()
}
        

function peek(): E{
  return linkedList.getLast()
}
        

public class MyStack<E> {

    private final MyLinkedList<E> list = new MyLinkedList<>();

    public MyStack(E[] elements){
        for (int i=0; i<elements.length; i++){
            list.addLast(elements[i]);
        }
    }

    public MyStack(){

    }

    public E pop(){
        if (list.isEmpty()) return null;
        return list.removeLast();
    }

    public void push(E e){
        list.addLast(e);
    }

    public E peek(){
        if (list.isEmpty()) return null;
        return list.getLast();
    }

    public boolean isEmpty(){
        return list.isEmpty();
    }

    public int getSize(){
        return list.getSize();
    }
}
        

class MyStack<E>() {
    
    private val list: MyLinkedList<E> = MyLinkedList()

    val isEmpty: Boolean
        get() = list.size == 0
    
    val size: Int 
        get() = list.size
    
    constructor(elements: Array<E>): this() {
        for (i in elements.indices) {
            list.addLast(elements[i])
        }
    }

    fun pop(): E? {
        if (list.empty) return null
        return list.removeLast()
    }


    fun push(e: E) {
        list.addLast(e)
    }

    fun peek(): E? {
        if (list.empty) return null
        return list.getLast()
    }
    
}
        

public class EvaluateExpression {

     public double evaluateExpression(String expression) {

        Stack<Double> operands = new Stack<>();
        Stack<Character> operators = new Stack<>();

        expression = expression.trim(); //remove every space in expression
        expression = insertBlanks(expression);

        String[] tokens = expression.split("\\s");

        for (String token : tokens) {

            if (!token.isEmpty()) {

                if (token.charAt(0) == '+' || token.charAt(0) == '-') {

                    while (
                            !operators.isEmpty() && (operators.peek() == '*' || operators.peek() == '-' || operators.peek() == '*' || operators.peek() == '/' || operators.peek() == '^')
                    ) {
                        processAnOperation(operators, operands);
                    }

                    operators.push(token.charAt(0));

                } else if (token.charAt(0) == '*' || token.charAt(0) == '/' || token.charAt(0) == '^') {

                    while (!operators.isEmpty() && (operators.peek() == '*' || operators.peek() == '/' || operators.peek() == '^')) {
                        processAnOperation(operators, operands);
                    }

                    operators.push(token.charAt(0));

                } else if (token.charAt(0) == '(') {

                    operators.push('(');

                } else if (token.charAt(0) == ')') {

                    while (operators.peek() != '(') {
                        processAnOperation(operators, operands);
                    }
                    operators.pop();

                } else {
                    operands.push(Double.parseDouble(token));
                }
            }
        }

        while (!operators.isEmpty())
            processAnOperation(operators, operands);

        return operands.pop();
    }


    private static void processAnOperation(Stack<Character> operators, Stack<Double> operands) {
        char op = operators.pop();
        double operand0 = operands.pop();
        double operand1 = operands.pop();

        switch (op) {
            case '*' -> operands.push(operand1 * operand0);
            case '/' -> operands.push(operand1 / operand0);
            case '-' -> operands.push(operand1 - operand0);
            case '+' -> operands.push(operand1 + operand0);
            case '^' -> operands.push(Math.pow(operand1, operand0));
        }
    }

    private static String insertBlanks(String s) {
        StringBuilder result = new StringBuilder();

        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == '(' || ch == ')')
                result.append(" ").append(ch).append(" ");
            else result.append(ch);
        }

        return result.toString();
    }
}
        

fun evaluateExpression(expression: String): Double {
    var expression = expression
    val operands = Stack<Double>()

    val operators = Stack<Char>()

    expression = expression.trim()   //remove every space in expression
    expression = insertBlanks(expression)


    val tokens = expression.split(Regex("\\s"))

    for (token in tokens) {

        if (!token.isEmpty()) {

            if (token[0] == '+' || token[0] == '-') {
                while (!operators.isEmpty() && (operators.peek() == '*' || operators.peek() == '-' || operators.peek() == '*' || operators.peek() == '/' || operators.peek() == '^')
                ) {
                    processAnOperation(operators, operands)
                }

                operators.push(token[0])
            } else if (token[0] == '*' || token[0] == '/' || token[0] == '^') {

                while (!operators.isEmpty() && (operators.peek() == '*' || operators.peek() == '/' || operators.peek() == '^')) {
                    processAnOperation(operators, operands)
                }

                operators.push(token[0])

            } else if (token[0] == '(') {
                operators.push('(')
            } else if (token[0] == ')') {

                while (operators.peek() != '(') {
                    processAnOperation(operators, operands)
                }

                operators.pop()

            } else {
                operands.push(token.toDouble())
            }
        }
    }

    while (!operators.isEmpty()) processAnOperation(operators, operands)

    return operands.pop()
}

private fun processAnOperation(operators: Stack<Char>, operands: Stack<Double>) {
    val op: Char = operators.pop()
    val operand0: Double = operands.pop()
    val operand1: Double = operands.pop()

    when (op) {
        '*' -> operands.push(operand1 * operand0)
        '/' -> operands.push(operand1 / operand0)
        '-' -> operands.push(operand1 - operand0)
        '+' -> operands.push(operand1 + operand0)
        '^' -> operands.push(operand1.pow(operand0))
    }
}

private fun insertBlanks(s: String): String {
    val result = StringBuilder()

    for (i in s.indices) {
        val ch = s[i]
        if (ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == '(' || ch == ')') result.append(" ")
            .append(ch).append(" ")
        else result.append(ch)
    }

    return result.toString()
}