The stack is a list that restricts insertion and deletion to be performed only in one position. This position is the end of the list, called the top of the stack. For the basic operations of the stack, there are push and pop. The former is insertion and the latter is delete.
The stack is also a FIFO table.
There are two types of implementations of stacks, one is to use arrays and the other is to use linked lists.
public class MyArrayStack<E> { private ArrayList<E> list = new ArrayList<>(); public void push(E e) { list.add(e); } public E pop() { return list.remove(list.size() - 1); } public E peek() { return list.get(list.size() - 1); } public boolean isEmpty() { return list.size() == 0; }}public class MyLinkStack<E> { LinkedList<E> list = new LinkedList<>(); public void push(E e) { list.addLast(e); } public E pop() { return list.removeLast(); } public E peek() { return list.getLast(); } public boolean isEmpty() { return list.size() == 0; }} Stack application
Balance symbol
Given a string of code, we check whether the brackets in this code comply with the syntax.
For example: [{()}] This is legal, but [{]}() is illegal.
The following is the test code:
public class BalanceSymbol { public boolean isBalance(String string) { MyArrayStack<Character> stack = new MyArrayStack<>(); char[] array = string.toCharArray(); for (char ch : array) { if ("{[(".indexOf(ch) >= 0) { stack.push(ch); } else if ("}])".indexOf(ch) >= 0) { if (isMatching(stack.peek(), ch)) { stack.pop(); } } } return stack.isEmpty(); } private boolean isMatching(char peek, char ch) { if ((peek == '{' && ch == '}') || (peek == '[' && ch == ']') || (peek == '(' && ch == ')')) { return true; } return false; } public static void main(String[] args) { BalanceSymbol symbol = new BalanceSymbol(); String string = "public static void main(String[] args) {BalanceSymbol symbol = new BalanceSymbol();}"; String string2 = "public static void main(String[] args) {BalanceSymbol symbol = new BalanceSymbol([);}]"; System.out.println(symbol.isBalance(string)); System.out.println(symbol.isBalance(string2)); }} Suffix expression
For example, a following input calculates the corresponding result,
3 + 2 + 3 * 2 = ?
This will produce different results in different calculation order. If the calculation result is 16 from left to right, and if the calculation result is 11 according to mathematical priority.
If the above infix expression is converted into a suffix expression:
3 2 + 3 2 * +
It would be very simple to calculate the value of this expression using a suffix expression, just use a stack.
Whenever a number is encountered, put the number on the stack.
Whenever an operator is encountered, two elements pop up to calculate according to the operator and then put them on the stack.
The only element that pops up the stack is the calculation result.
/** * Simplified version, each operand is only one, and assuming that the string is legal*/public class PostfixExpression { public static int calculate(String string) { MyArrayStack<String> stack = new MyArrayStack<>(); char[] arr = string.toCharArray(); for (char ch : arr) { if ("0123456789".indexOf(ch) >= 0) { stack.push(ch + ""); } else if ("+-*/".indexOf(ch) >= 0) { int a = Integer.parseInt(stack.pop()); int b = Integer.parseInt(stack.pop()); if (ch == '+') { stack.push((a + b) + ""); } else if (ch == '-') { stack.push((a - b) + ""); } else if (ch == '*') { stack.push((a * b) + ""); } else if (ch == '/') { stack.push((a / b) + ""); } } return Integer.parseInt(stack.peek()); } public static void main(String[] args) { System.out.println(calculate("32+32*+")); }} Convert an infix expression to a suffix expression
Suppose only the expressions +, -, *, /, () are run. And the expression is legal.
a + b * c - (d * e + f) / g The converted suffix expression is as follows:
abc * + de * f + g / -
The steps to use stack infix to convert suffixes are as follows:
import java.util.HashMap;import java.util.Map;public class ExpressionSwitch { private static Map<Character, Integer> map = new HashMap<Character, Integer>(); static { map.put('+', 0); map.put('-', 1); map.put('*', 2); map.put('/', 3); map.put('(', 4); } private static char[][] priority = { // Current operator// + - * / ( /* Stack + */{ '>', '>', '<', '<', '<'}, /* Top- */{ '>', '>', '<', '<', '<'}, /* Do* */{ '>', '>', '>', '>', '<'}, /* Make/ */{ '>', '>', '>', '>', '<'}, /* Character( */{ '<', '<', '<', '<', '<'}, }; public static String switch1(String string) { StringBuilder builder = new StringBuilder(); char[] arr = string.toCharArray(); MyArrayStack<Character> stack = new MyArrayStack<>(); for (char ch : arr) { if ("0123456789abcdefghijklmnopqrstuvwxyz".indexOf(ch) >= 0) { builder.append(ch); } else if ('(' == ch) { stack.push(ch); } else if (')' == ch) { while (true && !stack.isEmpty()) { char tmp = stack.pop(); if (tmp == '(') { break; } else { builder.append(tmp); } } } else { while (true) { if (stack.isEmpty()) { stack.push(ch); break; } char tmp = stack.peek(); if (isPriorityHigh(tmp, ch)) { builder.append(stack.pop()); } else { stack.push(ch); break; } } } } while(!stack.isEmpty()) { builder.append(stack.pop()); } return builder.toString(); } private static boolean isPriorityHigh(char tmp, char ch) { return priority[map.get(tmp)][map.get(ch)] == '>'; } public static void main(String[] args) { System.out.println(switch1("a+b*c-(d*e+f)/g")); }}Through this article, I hope everyone has mastered the knowledge of Java stack. Thank you for your support for this website!