Akik Look at that coder

Public account: Look at that code farmer

The last installment introduced the Flow control of Go language learning | Go Theme month

  • Definition of process control
  • Use if statements
  • Use the for statement
  • Use the switch statement
  • Use the defer statement
  • Use the break statement
  • Use the continue statement

This article will continue to take you into the world of Go.

1. Introduction to this paper

Go language learning power link – inverse Polish expression

Source: Leetcode150. Inverse Polish expression evaluation

2.

Evaluate the expression according to the inverse Polish notation.

Valid operators include +, -, *, and /. Each operand can be an integer or another inverse Polish expression.

Description:

Integer division preserves only integer parts. Given the inverse Polish expression is always valid. In other words, the expression always yields a valid value and never has a divisor of 0.

Example 1:

Input: tokens = ["2"."1"."+"."3"."*"] output:9Explanation: This expression is converted to the common infix arithmetic expression: (2 + 1) * 3) = 9
Copy the code

Example 2:

Input: tokens = ["4"."13"."5"."/"."+"] output:6Explanation: This expression is converted to the common infix arithmetic expression: (4 + (13 / 5=))6
Copy the code

Example 3:

Input: tokens = ["10"."6"."9"."3"."+"."11"."*"."/"."*"."17"."+"."5"."+"] output:22Explanation: This expression is converted to the common infix arithmetic expression: ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22
Copy the code

3. Ideas and methods:

For this problem we can think of stack way to solve.

  • By traversing the number group;
  • When the array traverses a number, the number is pushed onto the stack.
  • When the operation symbol is encountered, the two numbers on the top of the stack are taken out for calculation, and the calculation result is pushed into the stack again.
  • And so on until the array is iterated;
  • The last element in the output stack is the final answer.

Also notice the details of the problem, integer division only preserves integer parts.

4. Diagram force buckle:

From the above analysis, we use graphic method combined with the case to intuitively analyze the problem

For example: Enter tokens = [“2″,”1″,”+”,”3″,”*”]

When I =0, the array character iterated over is the number 2, and the number 2 is pushed onto the stack.

If I =1, the array character iterated over is the number 1, push the number 1 onto the stack.

When I =2, the array character iterated over is an operation symbol/, then take out the top two elements of the stack for divisible operation.

2/1 = 2

Push the result 2 of the top two elements onto the stack

When I =3, the array character iterated over is the number 3, pushing the number 3 onto the stack.

When I =4, the array characters iterated over are operation symbols*At this point, the two elements at the top of the stack are taken out for multiplication.

2 * 3 = 6

Push the result 6 of the top two elements onto the stack.

Array traversal is completed, the final output stack element is the result

5. The specific implementation code is as follows:

package main

import (
   "fmt"
   "strconv"
)

func evalRPN(tokens [5]string) int {
   stack := []int{}

   for _, token := range tokens {
      if num, err := strconv.Atoi(token); err == nil {
         stack = append(stack, num)
      } else {
         n2 := stack[len(stack)-1]
         n1 := stack[len(stack)-2]
         stack = stack[0 : len(stack)-2]

         switch token {
         case "+":
            stack = append(stack, n1+n2)
         case "-":
            stack = append(stack, n1-n2)
         case "*":
            stack = append(stack, n1*n2)
         case "/":
            stack = append(stack, n1/n2)
         }
      }
   }
   return stack[0]
}

func main(){

   var str=[5]string{"2"."1"."+"."3"."*"}
   fmt.Printf("The inverse Polish expression results as follows: %v",evalRPN(str))

}
Copy the code

The output is:

If you find this helpful:

1. Click “like” to support it, so that more people can see this article

2, pay attention to the public number: look at that code farmers, we study together and progress together.