Basic information Write the 2018 fall algorithm problem in Python

Purpose

--When I solved the past question, I made a mess of the algorithm problem. --I hate algorithm problems because it is complicated and troublesome ――But I have to review ... ――Then let's rewrite it in your favorite Python for a fun review!

Original problem

--Basic Information Technology Engineer Examination Fall 2018 Afternoon Question 8 --Click here for the question text (https://www.fe-siken.com/kakomon/30_aki/pm08.html) (Basic Information Technology Engineer Examination.com)

The program I wrote

--A program that receives an integer expression, calculates it, and returns a value

practice.py

Expression = []

formula = input("Please enter the formula:")

for j in range(len(formula)):
    Expression.append(formula[j])

Value = []
Operator = []
Priority = []

def calculation():
    OpCnt = 0
    Value.append(0)
    nest = 0

    #Analysis part
    for i in range(len(Expression)):
        chr = Expression[i]
        if chr >= '0' and chr <= '9':
            Value[OpCnt] = 10 * Value[OpCnt] + int(chr)

        if chr == '+' or chr == '-' or chr == '*' or chr == '/':
            Operator.append(chr)
            if chr == '+' or chr == '-':
                Priority.append(nest + 1)
            else:
                Priority.append(nest + 2)

            OpCnt = OpCnt + 1
            Value.append(0)

        if chr == '(':
            nest = nest + 10

        if chr == ')':
            nest = nest - 10

    #Calculation part
    while OpCnt > 0:
        ip = 0
        i = 1
        while i < OpCnt:
            if Priority[ip] < Priority[i]:
                ip = i
            i = i + 1
        chr = Operator[ip]
        if chr == '+':
            Value[ip] = Value[ip] + Value[ip + 1]
        if chr == '-':
            Value[ip] = Value[ip] - Value[ip + 1]
        if chr == '*':
            Value[ip] = Value[ip] * Value[ip + 1]
        if chr == '/':
            Value[ip] = Value[ip] / Value[ip + 1]
        i = ip + 1
        while i < OpCnt:
            Value[i] = Value[i + 1]
            Operator[i - 1] = Operator[i]
            Priority[i - 1] = Priority[i]
            i = i + 1
        OpCnt = OpCnt - 1
    return Value[0]

Let's disassemble it.

① Preparation

1-1. Have the expression entered and store it as a character in the Expression list.

practice.py

Expression = []

formula = input("Please enter the formula:")

for j in range(len(formula)):
    Expression.append(formula[j])

print(Expression)

--When you enter the formula 2 * (34-(5 + 67) / 8) given in the problem ...

console

['2', '*', '(', '3', '4', '-', '(', '5', '+', '6', '7', ')', '/', '8', ')']

--Each character is properly stored in the Expression list

1-2. Prepare 3 empty lists

--Value list: Stores the numerical part of the expression --Operator list: Stores the operator part of the expression --Priority list: Shows the priority of operators in the Operator list in descending order of values.

practice.py

Value = []
Operator = []
Priority = []

Next, let's look at the function part.

② Analysis processing and arithmetic processing

--The function is divided into an analysis processing part and an arithmetic processing part. --The function part just changed the writing style for Python --Example) Operator [OpCnt] ← Rewrite chr to Operator.append (chr)

practice.py

def calculation():
    OpCnt = 0
    Value.append(0)
    nest = 0

    #Analysis processing part
    for i in range(len(Expression)):
        chr = Expression[i]
        if chr >= '0' and chr <= '9':
            Value[OpCnt] = 10 * Value[OpCnt] + int(chr)

        if chr == '+' or chr == '-' or chr == '*' or chr == '/':
            Operator.append(chr)
            if chr == '+' or chr == '-':
                Priority.append(nest + 1)
            else:
                Priority.append(nest + 2)

            OpCnt = OpCnt + 1
            Value.append(0)

        if chr == '(':
            nest = nest + 10

        if chr == ')':
            nest = nest - 10

    #Calculation processing part
    while OpCnt > 0:
        ip = 0
        i = 1
        while i < OpCnt:
            if Priority[ip] < Priority[i]:
                ip = i
            i = i + 1
        chr = Operator[ip]
        if chr == '+':
            Value[ip] = Value[ip] + Value[ip + 1]
        if chr == '-':
            Value[ip] = Value[ip] - Value[ip + 1]
        if chr == '*':
            Value[ip] = Value[ip] * Value[ip + 1]
        if chr == '/':
            Value[ip] = Value[ip] / Value[ip + 1]
        i = ip + 1
        while i < OpCnt:
            Value[i] = Value[i + 1]
            Operator[i - 1] = Operator[i]
            Priority[i - 1] = Priority[i]
            i = i + 1
        OpCnt = OpCnt - 1
    return Value[0]

2-1. Analysis processing part

--Determine whether the value stored in the Expression list is a number, an operator, or a parenthesis --Determine the order of arithmetic processing --The contents of each list at the end of the analysis processing part are as follows.

Value = [2, 34, 5, 67, 8]
Operator = ['*', '-', '+', '/']
Priority =[2, 11, 21, 12]

--The operator has the highest priority in the expression in descending order of Priority value. --In this case, since Priority [2] is the maximum value, the operation using the operator of Operator [2] is performed first.

2-2. Arithmetic processing part

--Calculate in order based on the values in the Priority list --Set Value [0], which contains the final calculation result, as the return value. ――In this formula, you can receive the value of 50.0.

Impressions

――It was fun ^^