Being Programmer

Mars를 이용한 계산기 프로그램(괄호 연산 가능)

괄호 계산을 위해서 공부한 내용은 후위 표기법이었다. 중위 표기법은 *와 /가 +와 - 보다 더 우선순위가 높은 규칙을 따르기 때문에 우선 순위를 높이기 위해 괄호를 사용하지만 후위 표기법은 연산자의 위치에 따른 계산을 하기 때문에 구현하기가 더 쉬울 것이라 생각했다.

후위 표기법 변환 방법

후위표기법으로 바꾸는 규칙은 다음과 같다.
1. 수(operand)는 무조건 배열에 삽입
2. 여는 괄호 (가 나오면 무조건 스택에 push
3. 계산의 우선 순위는 *, / >>> +, - >>> ( 이다.
4. 연산자 스택이 비어있으면 연산자를 무조건 스택에 push
5. 연산자 스택에 있는 연산자가 우선순위가 더 높거나 같으면 스택에 있는 연산자를 pop해서 후위표기법 배열에 삽입하고 현재 연산자를 스택에 push. 현재 연산자의 우선순위가 더 높은 경우에는 연산자를 push만 한다.
6. 닫는 괄호 ')'가 나오면 '('를 만날 때까지 연산자를 pop해서 배열에 삽입
7. 수식이 종료되면 연산자 스택에 있는 모든 연산자를 pop해서 배열에 삽입

후위 표기법 변환 예시

수식 : 12 / ( 3 + 3 ) - 2

Code

변수 정의

    .data
sol:    .asciiz "= "
exp:    .word 0:100
size:    .word 100
st_op: .space 100        #연산자 스택
st_ans:    .space 100        #계산 스택
ar_pos:    .word 0:20        #후위 표기법 배열
error:    .asciiz "error"
nan:    .asciiz "Not a Number => operand2 of '/' must not be ZERO"

    .globl main
    .text

문제를 풀기 위해 사용된 대략적인 변수라고 할 수 있다. 컴퓨터 구조나 운영체제에서 배웠지만 프로그램 실행에 필요한 변수들은 모두 스택에 저장이 된다.

main 함수

main:
    la $a0 exp        #입력을 받아 $a0에 저장
    la $a1 size

    li $v0 8
    syscall

    la $s0 st_op        # $s0 = 연산자 스택의 주소
    li $s1 0        # 연산자 스택의 탑
    la $s2 st_ans        # $s2 = 계산과정 스택의 주소
    li $s3 0        # 계산과정 스택의 탑
    la $s4 ar_pos        #후위표기법을 위한 배열
    li $s5 0        #배열의 사이즈 측정
    jal convert
    jal operate
    jal print

    li $v0 10        #프로그램 종료
    syscall

프로그램의 메인함수이다. $v0에 8을 입력하고 system call을 하면 입력을 받는다.
그 이후에는 $s0, $s2, $s4에 연산자 스택, 계산과정 스택, 후위 표기법 저장을 위한 배열로 각각 정의한다.

후위 표기법 변환

convert:            #중위 표기법을 후위 표기법으로 변환
    addi $sp $sp -4    
    sw $ra 0($sp)

    li $t0 0        # $t0 = 입력값의 주소를 읽기 위해 더해주는 값을 저장하는 레지스터
    li $t2 0        # $t2 = 숫자 입력값이 있는지 알아보기 위한 값을 저장하는 레지스터
    li $t3 0        # $t3 = 입력된 수의 임시 저장 레지스터
    li $t9 10        # $t9 = 입력값의 자릿수를 만들어 주기 위한 값을 저장하는 레지스터

$t0는 수식이 저장된 배열의 포인터이다.
$t2는 연산자 전에 숫자 입력값이 있었는지 확인하는 플래그이다.
$t3은 여러 자리의 수를 만들기 위해 임시로 수를 저장하는 값이다.
$t9는 자릿수가 증가할 때마다 10을 곱해주기 위해서 사용된다.

load_input:            #입력값을 load
    add $t1 $t0 $a0
    lb $t1 0($t1)        # $t1 = 입력된 값을 한바이트씩 받아오는 레지스터
    addi $t0 $t0 1

    beq $t1 10 _ret_convert    # enter를 만나면 변환 종료  10 = \n
    beq $t1 '(' bracket    # 괄호를 만나면 bracket으로 이동
    beq $t1 '*' muldiv    # *나 /를 만나면 muldiv로 이동
    beq $t1 '/' muldiv
    beq $t1 '+' addsub    # +나 -를 만나면 addsub로 이동
    beq $t1 '-' addsub
    beq $t1 ')' close    #괄호가 닫히면 close로 이동

    blt $t1 47 error_print    # 숫자 또는 사칙연산이 아닌 경우
    bgt $t1 58 error_print

    addi $t1 $t1 -48    # 숫자를 정수형으로 고치기 위해 빼줌
    mul $t3 $t3 $t9        # '0'의 아스키 코드 값 = 48
    add $t3 $t1 $t3
    addi $t2 $t2 1        # $t2에 1을 더한다.

    j load_input        #load_input 반복

문자열을 순회하면서 입력 값에 따라 각각의 함수로 분기한다.

error_print:            # error를 출력하고 프로그램을 종료한다.

    la $a0 error
    li $v0 4
    syscall

    li $v0 10
    syscall

_ret_convert:    
    jal operand        # 숫자가 남아 있으면 숫자를 먼저 배열에 넣고
    jal pop_all        # 남은 연산자 모두를 pop해서 배열에 넣어준다.
    lw $ra 0($sp)
    addi $sp $sp 4

    jr $ra            # main으로 돌아간다.

입력 문자가 \\n인 경우 마무리 작업을 한다.

operand:
    bgt $t2 0 push_int    # $t2가 0보다 크다는 $t3에 숫자가 있다는 것을 의미한다.
                # 숫자가 있으면 정수를 배열에 넣어준다.
    jr $ra
push_int:        
    sll $t4 $s5 2        # 배열 사이즈에 4를 곱한 후 배열 주소에 더해
    add $t4 $s4 $t4        # 정수를 저장한다.
    sw $t3 0($t4)

    addi $s5 $s5 1
    li $t2 0        # 입력된 수가 없어진다는 것을 의미한다.
    li $t3 0        # 입력된 수를 초기화
    jr $ra            # oprand로 돌아가지 않고 각각의 함수로 돌아간다.
                # $ra의 값은 oprand 함수에 있는 $ra값과 같다.
                # 즉 $ra는 operand를 불러온 jal이 있는 주소 + 4 이다.

각각의 연산전에 수가 나왔다면 수를 먼저 후위 표기법 배열에 넣어준다.

bracket:            # 괄호는 무조건 push한다.
    jal operand

    j push
muldiv:                # muldiv는 스택의 탑에 저장된 연산자가 *나 /이면
                # 이전 것을 pop하고 자기 자신을 집어넣는다.
    jal operand

    beq $s1 0 push        # stack에 아무것도 없으면 push한다.

    lw $t5 0($s0)
    beq $t5 '+' push
    beq $t5 '-' push
    beq $t5 '(' push

    jal pop            # 이 경우는 이전 탑에 *나 /가 있던 경우이다.

    j muldiv

addsub:
    jal operand

    beq $s1 0 push        # stack에 아무것도 없으면 push한다.

    lw $t5 0($s0)
    beq $t5 '(' push    # (를 만나면 스택에 아무것도 없을 때와 같이 실행한다.

    jal pop            # 앞의 연산자들을 pop한다.

    j addsub
close:                # 괄호가 닫히면 '('를 만날 때 까지 pop한다.
    jal operand

    lw $t5 0($s0)
    beq $t5 '(' pop_bracket

    jal pop

    j close

push:                # 연산자를 스택의 탑에 넣는다.
    addi $s1 $s1 1
    addi $s0 $s0 4
    sw $t1  0($s0)

    j load_input

pop:                # 탑에 있는 연산자를 스택에서 꺼내 배열에 넣는다.
    lw $t5 0($s0)
    addi $s0 $s0 -4
    addi $s1 $s1 -1

    sll $t4 $s5 2
    add $t4 $s4 $t4
    mul $t5 $t5 -1        # 이 때 정수값들과 비교하기 위해 -를 곱해서 넣어준다.
    sw $t5 0($t4)

    addi $s5 $s5 1        # 배열의 크기 증가

    jr $ra
pop_bracket:            # '('는 후위 표기법의 배열에 필요 없으므로
                # 스택의 포인터만 낮춰준다. 
    addi $s0 $s0 -4

    addi $s1 $s1 -1
    j load_input

pop_all:            # 입력값을 모두 읽었으면 남아 있는 모든 연산자를 pop한다.
    addi $sp $sp -4
    sw $ra 0($sp)
    jal pop
    lw $ra 0($sp)
    addi $sp $sp 4
    bgtz $s1 pop_all    # 연산자 스택의 탑이 0보다 크면 다시 pop을 한다.

    jr $ra

후위 표기법 계산

operate:
    addi $sp $sp -4
    sw $ra 0($sp)

    li $t0 0        # 배열의 사이즈 만큼만 읽기 위한 count        

Loop:    
    seq $t6 $s3 1        # 스택에 값이 하나가 있고
    seq $t7 $t0 $s5        # count가 배열의 사이즈와 같으면 연산종료 
    and $t8 $t6 $t7
    beq $t8 1 _ret_operate
    beq $t7 1 error_print    # count가 배열의 사이즈와 같은데 스택의 탑이 1이 아니면 오류
                # 이 오류는 연산자 뒤에 바로 연산자가 올 때
                # 혹은 숫자 다음에 바로 '(' 나 ')' 가 올때 적용
    sll $t1 $t0 2        # count * 4
    add $t1 $s4 $t1        
    lw $t1 0($t1)
    addi $t0 $t0 1        # count++

    beq $t1 -45 op_sub    # '-' = 45
    beq $t1 -43 op_add    # '+' = 43
    beq $t1 -42 op_mul    # '*' = 42
    beq $t1 -47 op_div    # '/' = 47

    jal push_number        # 연산자가 아니라면 숫자를 push해준다.

    j Loop
push_number:
    addi $s2 $s2 4        # 스택에 한칸을 만들어 숫자를 저장
    sw $t1 0($s2)
    addi $s3 $s3 1        # Top Of Stack ++

    jr $ra

op_add:                
    lw $t2 0($s2)        # 탑에 있는 값을 pop해서 opernad 2로 설정
    addi $s2 $s2 -4        # Top of Stack --
    addi $s3 $s3 -1    
    lw $t3 0($s2)        # 다시 탑에 있는 값을 pop 해서 oprand 1로 설정
                # 이 주소에 다시 저장해야 되기 때문에 Top of Stack --를 안함
    add $t4 $t3 $t2        # operand 1 + opernad 2
    sw $t4 0($s2)        # 스택의 탑에 값을 저장

    j Loop
op_sub:
    lw $t2 0($s2)        # 탑에 있는 값을 pop해서 opernad 2로 설정
    addi $s2 $s2 -4        # Top of Stack --
    addi $s3 $s3 -1        
    lw $t3 0($s2)        # 다시 탑에 있는 값을 pop 해서 oprand 1로 설정
                # 이 주소에 다시 저장해야 되기 때문에 Top of Stack --를 안함

    sub $t4 $t3 $t2        # operand 1 - operand 2
    sw $t4 0($s2)        # 스택의 탑에 저장

    j Loop
op_mul:                
    lw $t2 0($s2)        # 탑에 있는 값을 pop해서 opernad 2로 설정
    addi $s2 $s2 -4        # Top of Stack --
    addi $s3 $s3 -1
    lw $t3 0($s2)        # 다시 탑에 있는 값을 pop 해서 oprand 1로 설정
                # 이 주소에 다시 저장해야 되기 때문에 Top of Stack --를 안함

    mul $t4 $t3 $t2        # operand 1 * opernad 2
    sw $t4 0($s2)        # 스택의 탑에 저장

    j Loop
op_div:
    lw $t2 0($s2)        # 탑에 있는 값을 pop해서 opernad 2로 설정
    addi $s2 $s2 -4        # Top of Stack --
    addi $s3 $s3 -1
    lw $t3 0($s2)        # 다시 탑에 있는 값을 pop 해서 oprand 1로 설정
                # 이 주소에 다시 저장해야 되기 때문에 Top of Stack --를 안함

    beqz $t2 NaN_print    # 분모가 0이 되면 오류
    div $t4 $t3 $t2        # operand 1 / operand 2
                # 단 여기서 나머지는 계산되지 않음
    sw $t4 0($s2)        # 스택의 탑에 저장

    j Loop

NaN_print:
    la $a0 nan        # 오류메시지 출력
    li $v0 4
    syscall

    li $v0 10        # 프로그램 종료
    syscall
_ret_operate:            # main 으로 돌아감

    lw $ra 0($sp)
    addi $sp $sp 4

    jr $ra

print:                # 마지막 계산된 값을 print
    la $a0 sol
    li $v0 4
    syscall

    lw $a0 0($s2)
    li $v0 1
    syscall

    jr $ra

예외 처리

1. 괄호를 제외한 연산자 2개가 연속되는 경우
2. 연산자의 수가 초과되는 경우    ex. "5+4*" 
3. 곱셈을 생략하는 경우    ex. 5(3+2)
4. 숫자나 연산자가 아닌 다른 문자가 수식에 있는 경우
5. 나눗셈을 할 때 분모가 0인 경우

프로그램의 한계점

1. 정수 계산기이다.
    나눗셈의 결과값은 정수가 된다. 예를 들어 15/4는 3.75가 아니라 3으로 계산된다.
2. 음수는 입력을 받을 때 (0-5)와 같은 형태를 취해야 한다.

프로그램을 짜면서 int() 같은 함수에도 감사함이 느껴졌다. 괄호 연산 또한 고급 언어에서는 기본적으로 가능하기 때문에 구현이 복잡할 거라 생각하지 못했다. Mars를 이용해 디버깅을 하면서 컴퓨터 구조 시간에 배웠던 것 처럼 데이터가 스택에 저장되어 어떻게 사용이 되고 레지스터를 이용해서 데이터를 저장하는 등의 이론적인 부분에 이해도가 높아지는 기분이었다.

내가 이 코드를 작성할 때는 오직 신과 나만이 그것이 무엇을 하는 코드인지 알았다 하지만 지금은... 오직 신만이 안다

[Python] 자료형 - (3) 리스트

리스트는 길게 이어진 상자라고 생각하면 된다. 우리는 리스트 안에 숫자, 문자열, 새롭게 정의한 객체 등 다양한 자료형을 넣을 수 있는 상자이다.

리스트의 생성

a = []
b = list()
c = [1, 2, 3]
d = ["Hello", "World"]
e = [1, 2, "Hello", "World"]
f = [[1, 2], ["Hello", "World"]]

a와 b리스트는 빈 리스트를 생성해주는 것이다. e 리스트 처럼 상자마다 다른 자료형을 삽입할 수도 있고 f 리스트처럼 리스트를 삽입할 수도 있다.

리스트의 사용

리스트에 보관된 데이터를 어떻게 사용할 것인가

인덱싱

리스트 명[위치값]의 형태로 리스트 안의 원소에 접근이 가능하다. 이것을 인덱싱이라 한다. 리스트는 0번째 칸부터 저장이 되는 것을 주의해야 한다.

a = [10, 20, 30, 40]
print(a[0])
print(a[3])
print(a[-1])
print(a[4])

인덱스 값으로 음수값을 주면 뒤에서부터 원소를 접근한다. 리스트의 크기는 4이지만 리스트의 마지막 번호는 3이기 때문에 a[4]를 사용하면 에러가 난다. 리스트의 범위를 벗어난 접근에 대한 에러다.

슬라이싱

리스트는 꼭 원소를 하나씩 접근할 필요가 없다. 내가 필요한 부분만 잘라서 리스트를 사용하고 싶을 때는 슬라이싱을 사용한다. 리스트를 토막낸다고 생각하면 된다.
기본적인 형태는 리스트 명[시작 인덱스: 끝나는 인덱스 + 1] 과 같이 사용된다. 시작 인덱스와 마지막 인덱스는 생략이 가능하고 그런 경우 끝에서 시작 또는 끝에서 끝남을 의미한다.

a = [1, 2, 3, 4, 5, 6, 7, 8, 9]
b = a[:5]
c = a[5:]
d = a[2:7]
print(a)
print(b)
print(c)
print(d)

사용을 할 때는 : 뒤의 값 전까지 슬라이싱을 하는 것을 명심해야 한다.

리스트의 연산

리스트 역시 문자열처럼 리스트끼리 더하기와 곱하기 연산이 가능하다.

a = ['a', 'b', 'c']
b = ['d', 'e', 'f']
print(a + b)
print(a * 3)

수정, 삭제

a = [1, 2, 3]
a[2] = 4
print(a)

리스트는 직접적으로 값을 바꿀 수 있는 mutable 자료형이다.

a = [1, 2, 3]
del a[1]
print(a)

del 함수는 파이썬의 기본 함수로 객체를 삭제하는 함수이다.

문자열이란

문자열(String)이란 문자를 나열해 놓은 것을 의미한다. 문자는 a, b, c 같은 알파벳과, 가나다 같은 한글, 1,2,3 같은 숫자,!@#같은 특수문자 등 유니코드 내에 문자를 의미한다.

"Hello World"
"123456789"
"010-1234-5678"
"!@#$"

문자열의 표현

파이썬에서는 문자열을 쌍따옴표"로도 나타낼 수 있지만 작은 따옴표'로 나타낼 수도 있다.

str1 = "abc"
str2 = 'abc'
print(True if str1 == str2 else False)

위 예제의 print함수는 두 문자열이 같으면 True를 다르면 False를 출력하는 함수입니다. 두 문자열은 그 내부적으로는 서로 같습니다. 파이썬 내부에서는 기본적으로 문자열을 작은 따옴표로 묶여 있는 것으로 표시된다.

위의 방법 외에도 여러 줄의 문자열을 위해서 여러 줄의 문자열을 한 번에 나타내는 방법이 있다.
큰 따옴표나 작은 따옴표를 3개를 사용해서 나타낸다.
첫번째 줄

str3 = """첫 번째 줄
두 번째 줄
세 번째 줄
"""
print(str3)

이스케이프 문자

이스케이프 문자란 줄바꿈, 띄워쓰기 등 여러 기능을 위해 미리 정해놓은 문자 집합이다..
가장 자주 볼 수 있는 문자는 \n, \t, \\이 있다.

str4 = "첫번째\n두번째\n세번째"
str5 = "1\t2\t3\t4"
str6 = "8\t9\t10\t11"
print(str4)
print(str5)
print(str6)

문자열의 연산

문자열 더하기(Concatenation)

문자열은 문자열끼리 더하기가 가능하다. 문자열의 덧셈은 각 요소를 더하는 것이 아니라 문자열 뒤에 문자열을 추가한다고 생각하면 된다.

str1 = "Hello"
str2 = " World"
str3 = str1 + str2
print(str3)

문자열 곱셈(반복)

문자열의 곱셈은 곱하는 수만큼의 반복을 의미한다.

str1 = 'Hello '
str2 = str1 * 3
print(str2)

2 * 3 = 2 + 2 + 2 인 것을 생각해보면 문자열의 곱셈이 의미하는 것을 알 수 있다. str2 = str1 + str1 + str1이므로 "Hello "라는 문자열을 3번 이어붙인 것이다.

문자열의 기본 함수에 대해서는 다음에 포스팅하겠습니다.

[파이썬] 자료형 - (1) 숫자형

숫자형은 우리가 사용하는 숫자(number)를 나타내는 자료형입니다.
예를 들어 1234나 -1234 같은 정수형과 12.34 같은 실수형이 대표적인 표현 방법이며 2진수, 8진수, 16진수로 나타낸 수도 수를 표현하는 방법입니다.

정수형

정수형은 우리가 가장 잘 아는 양의 정수, 음의 정수, 0을 뜻하는 자료형입니다.

a = 123
b = -178
c = 0

위에서 a, b, c 모두 정수를 의미합니다.

진법

파이썬에서 기본 제공되는 진법 표기는 2진수, 8진수, 16진수가 있습니다.

base_2 = 0b1111
base_8 = 0o0017
base_16 = 0x000F
base_10 = 15

print(base_2, type(base_2))
print(base_8, type(base_8))
print(base_16, type(base_16))
print(base_10, type(base_10))

위의 모든 값들은 print()함수에 넣게 되면 정수 값인 15를 출력하고 type() 함수의 출력을 보면 모두 int로 출력됩니다. 눈으로 보기에는 다른 수 같지만 컴퓨터의 입장에서는 모두 같은 수이기 때문입니다.

<출력 결과>

실수형

실수형은 소수점이 포함된 숫자를 의미합니다.

f1 = .1
f2 = 0.1
f3 = -3.14
f4 = 1.23e4

f1처럼 소수점 앞의 0은 생략이 가능합니다. 1.23e4은 지수 표현 방식이라고 합니다. $$ 1.23 * 10^4 $$을 의미하고 소문자 e, 대문자 E 모두 사용이 가능합니다. 알고리즘 문제를 풀면서 무제한 값을 설정할 때 1e9와 같은 수를 많이 쓰기도 합니다.

[CodeUp] Python 기초100제 - 6009

6009 : [기초-입출력] 문자 1개 입력받아 그대로 출력하기

문제

문제 출처 : codeup.kr/problem/php?id=6009

Code

c = input()
print(c)