자료구조 5-2장 | Linear Data Structure | 숙명여대 학점교류

학점교류로 듣는 숙명여대 자료구조

day 4. 2021.12.27. 월

 

---

INTRO

선형 큐를 리스트로 만들었다.

반면, Circular Queue는 None 만큼의 사이즈를 만들었다. 

Expression Evaluation 수식 변환

an expression consists of 

operator = arithmetic, logical, assignment

operand = variable, constant

 

types of expression notation

depends on operator position against operand

• infix notation : a/b - c+d*e-a*c
• postfix notation : a b / c - d e * + a c * -
• prefix notation : - + - / a b c * d e * a c

 

Infix vs postfix

• Infix notation for human : 3 + 5 * 7

each operator has its own precedence

parentheses change the priority of evalutation

evaluation happens at any position of expression

: 결합성에 의해서 left-to-right로 결합해주게 된다. assotivity

 

• postfix notation for compiler : 3 5 7 * + 

no precedence of operator

no parenthesis

expression is always calculated from left to right

 

postfix evaluation

 

due to the absence of parentheses, it is simpler to evaluate postfix than infix

not intuitive for human

infix expression should be converted into postfix before calculation

(prefix conversion)

 

example

infix
=>
postfix
=> 
prefix

2 + 3 * 4
=>
2 3 4 * +
=> 
+ 2 * 3 4

a * b + 5
=> 
a b * 5 +
=>
+ * a b 5

(1+2)*7
=>
1 2 + 7 *
=>
* + 1 2 7

a * b / c
=>
a b * c /
=>
/ * a b c

a / (b - c + d) * (e - a) * c
=> 
a b c - d + / e a - c *
=>
* * / a + -  b c d - e a c

a / b - c + d * e - a * c
=>
a b / c - d e * + a c * -
=> 
- + - / a b c * d e * a c

postfix evaluation

 

* postfix : 6 2 / 3 - 4 2 * +

get a token from expr string from left to right

if a token is operand, push it into stack

if an operator, pop and calculate two operands with the operator

cf) operator = '/', pop() = 2, pop() = 6인 경우, 6 / 2를 해주어야 함 주의

push the result back into stack

 

end of string이 들어오면 끝났다는 것을 알 수 있다. 

마지막으로 남아있는 값이 수식의 결과값이다. 

 

* functions

a postfix expression stored in a string

getSymtype()

returns a sym_type (0~8) together with a char symbol(문자열을 읽어온다)

string에서 토큰을 읽어와서 종류를 가져온다. 

 

eval_postfix() : main function

if token is operand => push

if token is operator => pop, pop, evaluate, push

 

* code

function : infix -> postfix -> evaluation

expr : no space

operator : (, ), +, -, *, /, %

operand : 0~9 // single digit

 

class Sym:
    OPEN_B = 1
    CLOSE_B = 2
    PLUS = 3
    MINUS = 4
    TIMES = 5
    DIVIDE = 6
    MOD = 7
    OPERAND = 8

class Expression:
    def __init__(self):
        self.stack = []
        self.size = 100
        self.expr = ""
        self.top = -1
    def eval_postfix(self):
        for sym in self.expr:
            print(sym, end=' ')
            sym_type = self.getSymtype(sym)
            if sym_type == Sym.OPERAND: self.push(int(sym))
            else:
                op2 = self.pop()
                op1 = self.pop()
                if sym_type == Sym.PLUS:
                    self.push(op1 + op2)
                elif sym_type == Sym.MINUS:
                    self.push(op1 - op2)
                elif sym_type == Sym.TIMES:
                    self.push(op1*op2)
                elif sym_type == Sym.DIVIDE:
                    self.push(op1 // op2)
                elif sym_type == Sym.MOD:
                    self.push(op1 % op2)
        return self.pop()
    
    def getSymtype(self, sym):
        if sym == '(' : sym_type = Sym.OPEN_B
        elif sym == ')' : sym_type = Sym.CLOSE_B
        elif sym == '+' : sym_type = Sym.PLUS
        elif sym == '-' : sym_type = Sym.MINUS
        elif sym == '*' : sym_type = Sym.TIMES
        elif sym == '/' : sym_type = Sym.DIVIDE
        elif sym == '%' : sym_type = Sym.MOD
        else: sym_type = Sym.OPERAND
        return sym_type
    
e = Expression()
print("수식 : ", e.expr)
print()
print("resulut = ", e.eval_postfix())

 

 

Infix to postfix conversion

 

Manual method

parenthesize each operation in expr

move an operator soas to replace its closest right bracket

delete all remaining brackets

=> multiple scan을 해주어야 해서 비효율적이다. 

a / b - c + d * e - a * c
((((a/b)-c)+(d*3))-(a*c))
((((ab/c-(de*+(ac*-
ab/c-de*+ac*-

 

algorithm for single scan conversion

operand order must not be changed

according to precedence, operators are pushed in stack

until finding their proper positions in postfix

 

Infix to postfix conversion

operand is just printed out as it is

operator rule, token (T)

a는 그대로 출력한다. 

operator rule은

if empty stack or token > top, then push(token)

if token <= top, then pop() and push(token)

if token==eos, then pop and print out all remaining operators from stack

 

ex1) a+ b * c

ex2) a* b + c

 

ㅇㅎ 그렇군

stack을 꺼내라. 

equal인 경우, 연산 순위가 같을 때에도 스택에서 꺼내라. 

스택이 어떤 역할을 하는가. 

abc*+ 연산자가 *+로 바뀌고, ab*c+로 바뀐다. 

연산자의 위치를 바꾸는 역할을 해준다. 

중위 수준의 연산자가 후위 수준에서 역할을 하도록 해준다. 

재조정하도록 역할을 해준다. 

 

parenthesized infix expressions (sub expressions)

괄호는 전체 수식에서 부분 수식이 시작되는 것과 같다. 

 

--- rule ---

> if token is entered

>>> if empty stack of T > top : then push(T)

>>> elif T <= top : then pop(top) and push(T)

>>> if T == '(' : push('('), and next incoming tokens are pushed with respecting above rules

>>> if T == ')': then pop all operators until reaching '(', and '(' is discarded without being printed

>>> if T == eos : then pop and print out all remaining operators in stack

 

괄호는 부분 수식의 시작

왼쪽 괄호 일단 넣음

오른쪽 괄호 나오면, 왼쪽 괄호 나올 때까지 출력하고, 왼괄호를 버린다. 

 

example ) a * (b + c) * d

example ) a + (b * c + d) * e

 

연습해보기

class Sym:
    OPEN_B = 1
    CLOSE_B = 2
    PLUS = 3
    MINUS = 4
    TIMES = 5
    DIVIDE = 6
    MOD = 7
    OPERAND = 8

class Expression:
    def __init__(self):
        self.stack = []
        self.size = 100
        self.expr = ""
        self.top = -1
    def eval_postfix(self):
        for sym in self.expr:
            print(sym, end=' ')
            sym_type = self.getSymtype(sym)
            if sym_type == Sym.OPERAND: self.push(int(sym))
            else:
                op2 = self.pop()
                op1 = self.pop()
                if sym_type == Sym.PLUS:
                    self.push(op1 + op2)
                elif sym_type == Sym.MINUS:
                    self.push(op1 - op2)
                elif sym_type == Sym.TIMES:
                    self.push(op1*op2)
                elif sym_type == Sym.DIVIDE:
                    self.push(op1 // op2)
                elif sym_type == Sym.MOD:
                    self.push(op1 % op2)
        return self.pop()
    
    def getSymtype(self, sym):
        if sym == '(' : sym_type = Sym.OPEN_B
        elif sym == ')' : sym_type = Sym.CLOSE_B
        elif sym == '+' : sym_type = Sym.PLUS
        elif sym == '-' : sym_type = Sym.MINUS
        elif sym == '*' : sym_type = Sym.TIMES
        elif sym == '/' : sym_type = Sym.DIVIDE
        elif sym == '%' : sym_type = Sym.MOD
        else: sym_type = Sym.OPERAND
        return sym_type
    def pop(self):
        return self.stack.pop()
    def push(self, data):
        self.stack.append(data)
    def isEmpty(self):
        return len(self.stack)==0
    def infix_postfix(self, expr):
        for token in expr:
            print(token, end=' ')
            # isalnum - 알파벳이나 수 operand
            if token.isalnum(): self.expr += token
            elif token=='(': self.push(token)
            elif token==')':
                sym = self.pop()
                while sym != '(':
                    self.expr += sym
                    sym = self.pop()
            else:
                # 스택 연산자 우선순위 비교함
                while not self.isEmpty() and\
                    self.precedence(self.stack[-1]) >= self.precedence(token):
                        sym=self.pop()
                        self.expr += sym
                self.push(token)
        while not self.isEmpty():
            self.expr += self.pop()
    def precedence(self, op):
        if op == '(' : return 0
        elif op in ['+', '-']: return 1
        elif op in ['*', '/', '%']: return 2

    
e = Expression()
expr = '9/(3+6-5)*7*(6-4)'
e.infix_postfix(expr)

print("수식 : ", e.expr)
print()
print("resulut = ", e.eval_postfix())

postfix, infix

 

 

Maze Problem 미로

representation of a maze

problem :  find a path from entrance to exit

'0' for open path, '1' for closed path

movable in straight direction - 전후좌우 대각선

 

 

a maze is surrounded by boundaries

maze[m][p] 2차원 배열을 활용한다. 

경계를 검사할 필요가 없다. 

 

to find any open path, 

4 directions are searched in clockwise order of NESW using move[0] ~ move[3] offsets

maze[next_row][next_col]

next_row = row + y

next_col = col + x

 

remember if visited

mark[[0] * 10 for i in range(10)] list comprehension을 이용해서 mark 배열을 하였다. 

재방문하지 않도록 한다. 

재방문을 허용하지 않기 위해서 마크라는 배열을 만들었다. 

10*10

 

path stack

stack을 이용해서 문제를 풀게 된다. 

경로 스택인데, 어떤 위치에 있다가 다른 곳으로 간다면? 

현재 위치를 버리고 가는 게 아니라, 어디에 저장해두고 간다. 

항상 현재 포지션을 가지고 간다. 그래야 되돌아갈 수 있다. 

whenever moving to a new position, current position must be saved in stack for backtracking

row, col (of current position)

if no more path to go, a saved position is popped from stack and contonue to search from that position

if path stack is empty escaping fails

 

path stack이 비었다는 게 무슨 말이지?

 

미로를 헤매다가 탈출구 위치에 도달하면 탈출

갈 곳이 없으면 탈출 실패

 

알고리즘 : 새로운 위치로 갈떄

나의 위치를 스택에 넣어둔다. 

그리고 동서남북을 try해보고, 다른 스택을 해본다. 안되면, 이전 위치로 돌아간다. 

 

analysisTC = O(M*P)

 

로봇 같은 것 개발할 때도 같은 것을 한다. 

나중에 저장한 위치로 저장하기 위해서 스택을 쓴다

스택 = 뒤로가기용

class Maze:

    def __init__(self):
        self.maze=[[1, 1, 1, 1, 1, 1, 1, 1, 1, 1 ], \
        [1, 0, 0, 1, 0, 0, 0, 0, 1, 1 ], \
        [1, 1, 0, 1, 0, 1, 1, 0, 0, 1 ], \
        [1, 0, 0, 0, 0, 1, 1, 1, 1, 1 ], \
        [1, 0, 1, 1, 0, 1, 0, 0, 0, 1 ], \
        [1, 0, 0, 1, 0, 1, 1, 0, 1, 1 ], \
        [1, 1, 0, 0, 1, 0, 0, 0, 1, 1 ], \
        [1, 1, 1, 0, 0, 0, 1, 0, 0, 1 ], \
        [1, 0, 0, 0, 1, 0, 1, 1, 'X', 1 ], \
        [1, 1, 1, 1, 1, 1, 1, 1, 1, 1 ]]
        self.mark=[]
        self.stack = []
        self.found = False

    def empty(self):
        return len(self.stack)==0
    def push(self, row, col):
        self.stack.append((row, col))
    def view(self):
        print("stack", self.stack)

    def explore(self):
        self.mark[1][1] = 1 # 방문해서 1로 바꾼다
        self.push(1,1)
        while not self.empty() and not self.found:
            if not move_next:
                # 다시 이전 위치로 돌아가서 탐색한다. 
                row, col = self.stack.pop()
            move_next = False
            for x, y in [(0,-1),(1,0),(0,1), (-1,0)]: # 북, 동, 남, 서
                next_col = col + x
                next_row = row + y
                if self.maze[next_row][next_col] == 'X':
                    self.push(row, col)
                    self.push(next_row, next_col)
                    self.found = True
                    # 탈출 성고
                    break
                elif self.maze[next_row][next_col]==0 and self.mark[next_row][next_col]==0:
                    # 아직 도착 못함
                    # 아직 기회 남음.
                    self.mark[next_row][next_col]=1
                    print(next_row, next_col, "is visited")
                    self.push(row, col)
                    row = next_row
                    col = next_col
                    move_next = True
                    break
        if not self.found: 
            print("No path found")
        else: 
            print("Path found:")
            self.view() # 거쳐간 경로 출력함