Data structure and algorithm analysis of flight diary — Stack and Four Operations

This example shows how to use a stack to perform a simple four-rule operation.

Expression of prefix, infix, and suffix for four operations (inverse Polish operation)
  • Prefix expression calculation method:(3 + 4) x 5-6 >>> - x + 3 4 5 6Scan from right to left, when the number is pressed into the number stack, when the operator is encountered, two numbers pop up on the top of the number stack and make corresponding operations, and the calculation result is pushed into the stack; Repeat the process until the left end of the prefix expression;
  • Infix expression calculation method: the normal expression is the infix expression.
  • Postfix expression calculation method:6 x(5 +(2 +3) x8) >>> 6 5 2 3 + 8 x + xScan from left to right, when the number is pressed into the number stack, when the operator is encountered, two numbers pop up on the top of the number stack and make corresponding operations, and the calculation result is pushed into the stack; Repeat the process until you reach the right end of the prefix expression;
  • Code implementation: through the given suffix expression, the use of stack to complete the calculation (including multi-digit and decimal point, not including negative numbers);
package LeetCodeAQ; import java.util.*; Public class PolandNotation {public static void main(String[] args) {// Enter suffix expressions separated by Spaces for each number and notation (1-2*3) + ((5*3-1) *2-1) String suffixExpression = "1 2 3 * - 5 3 * 1 - 2 * 1 - +"; List<String> resList = getList(suffixExpression); System. The out. Println (" result = "+ resList); float res = calculate(resList); System.out.println(" result ="+ res); Public static List<String> getList(String suffixExpression){String[] split = suffixexpression.split (" "); List<String> list = new ArrayList<String>(); for(String s:split){ list.add(s); } return list; Public static float calculate(List<String> List) {Stack<String> Stack = new Stack<>(); public static float calculate(List<String> List) {Stack<String> Stack = new Stack<>(); For (String item:list) {// Matches ("^[+-]? \\d+(\\.\\d+)? $")) { stack.push(item); }else { float num1 = Float.parseFloat(stack.pop()); float num2 = Float.parseFloat(stack.pop()); float res = 0; if(item.equals("+")) { res = num1 + num2; }else if(item.equals("-")) { res = num2 - num1; }else if(item.equals("*")) { res = num1 * num2; }else if(item.equals("/")){ res = num2 / num1; }else {throw new RuntimeException(" wrong "); } stack.push(String.valueOf(res)); } } return Float.parseFloat(stack.pop()); }}Copy the code

Next lecture we’ll see how to convert an infix expression to a suffix expression. Okay? And among them train of thought, difficulty and note!

Quiet and Quick, Salute!