The order of the elements in the stack is first in, then out. The added elements are always at the top of the stack, and the removed elements are first out of the stack, just like the magazine. Infix expressions are the way we evaluate expressions like (2*3-2)*(3+3*3) we always take precedence over parentheses, * / takes precedence over + –

The idea behind using a stack structure to calculate this expression is to have two stacks, one for numbers and one for symbols.

package com.dfsn.cloud.eureka; public class Stack<T> { private Object arr[]; private int top = -1; public Stack(int capacity) { arr = new Object[capacity]; } public void push(T T) {if (isFull()) {throw new RuntimeException(" stack isFull, can't add "); } top++; arr[top] = t; } public T pop() {if (isEmpty()) {throw new RuntimeException(" stack empty, no element "); } return (T) arr[top--]; } public T peek() {if (isEmpty()) {throw new RuntimeException(" stack empty, no element "); } return (T) arr[top]; } public boolean isEmpty() { return top == -1; } public boolean isFull() { return top == arr.length - 1; } public void show() { for (int i = 0; i <= top; i++) { System.out.println(arr[i]); } } public int size() { return top + 1; }}Copy the code

View Code

 

package com.dfsn.cloud.eureka; Public class NifixExpression {public int calculate(String expression) {Stack<Integer> numberStack specifies a maximum of 10 digits  = new Stack<>(10); Stack<String> symbolStack = new Stack<>(9); for (int i = 0; i < expression.length(); i++) { String current = expression.substring(i, i + 1); Int symbolOrNumber = symbolOrNumber(current); If (symbolOrNumber == 0) {// If (symbolOrNumber == 0) { Int concatNumber = concatNumber(expression.substring(I)); I +(123. Length) +(concatNumber +(123. Length) +(123 "").length() - 1; // Add numberstack. push(concatNumber); } else {if (symbolstack.isempty ()) {// If (symbolstack.isempty ()) {// If (symbolstack.isempty ()); } else {// If (current. Equals ("(")) {symbolstack.push (current); continue; } // If it is a close parenthesis, you need to pop up one symbol and two digits at a time until you hit (end of symbol, Equals (")") {while (true) {if (symbolstack.peek ().equals("(")) {symbolstack.pop (); break; } else { int number2 = numberStack.pop(); int number1 = numberStack.pop(); String symbol = symbolStack.pop(); int result = operation(number1, number2, symbol); numberStack.push(result); } } continue; String stackTop = symbolstack.peek (); String stackTop = symbolstack.peek (); String stackTop = symbolstack.peek (); int stackTopPriority = priority(stackTop); int priority = priority(current); // If (priority > stackTopPriority) {symbolstack.push (current); } else {// If the current symbol priority is less than or equal to the top of the stack operator priority, then pop a symbol from the top of the stack // pop two digits from the stack to do the operation note: Int number2 = numberstack.pop (); int number1 = numberStack.pop(); String symbol = symbolStack.pop(); int result = operation(number1, number2, symbol); numberStack.push(result); symbolStack.push(current); While (true) {if (symbolstack.isempty ()) {break; while (true) {if (symbolstack.isempty ()) {break; } else { int number2 = numberStack.pop(); int number1 = numberStack.pop(); String symbol = symbolStack.pop(); int result = operation(number1, number2, symbol); numberStack.push(result); } } if (numberStack.size() ! = 1) {throw new RuntimeException(" operation exception "); } else { return numberStack.pop(); }} // Return 1 to indicate that it is the operator, Returns 0 means is digital public int symbolOrNumber (String expression) {if (expression) equals (" + ") | | expression. The equals (" - ") | | expression.equals("*") || expression.equals("/") || expression.equals("(") || expression.equals(")")) { return 1; } else if (expression.equals("0") || expression.equals("1") || expression.equals("2") || expression.equals("3") || expression.equals("4") || expression.equals("5") || expression.equals("6") || expression.equals("7") || expression.equals("8") || expression.equals("9")) { return 0; } else {throw new RuntimeException(" not a number or operator "); }} / / returns the operator level * / high public int priority (String symbol) {if (symbol) equals (" + ") | | symbol. Equals (" - ")) {return 1; } else if (symbol.equals("*") || symbol.equals("/")) { return 2; } else if (symbol.equals("(")) { return 0; } else {throw new RuntimeException(" unrecognized operator "); Public int concatNumber(String STR) {StringBuilder strNumber = new StringBuilder(); int index = 0; while (true) { if (index > str.length() - 1) { break; } String ch = str.charAt(index) + ""; if (symbolOrNumber(ch) == 0) { strNumber.append(ch); index++; } else { break; } } return Integer.parseInt(strNumber.toString()); Public int operation(int number1, int number2, String symbol) {switch (symbol) {case "+": return number1 + number2; case "-": return number1 - number2; case "*": return number1 * number2; case "/": return number1 / number2; Default: throw new RuntimeException(" operator not correct "); }}}Copy the code

View Code