❓ 문제

1918번: 후위 표기식

정답율이 33% 정도이지만 Stack을 사용해 푸는 문제라 과감하게 도전했다.

그리고 언제나 조져지는 건 나였다…

전위, 중위, 후위 표기법을 처음 들어보기도 했고 Stack을 사용하는 문제는 처음이라 거의 푸는 방법을 보고 알고리즘을 짰다.

⌨️ 전체 코드

package main

import "fmt"

//Stack 구현
type Stack struct {
	stack []rune
}

func (s Stack) IsEmpty() bool {
	return len(s.stack) == 0
}

func (s *Stack) Pop() {
	if !s.IsEmpty() {
		s.stack = s.stack[:len(s.stack)-1]
	}
}

func (s *Stack) Push(v rune) {
	s.stack = append(s.stack, v)
}

func (s *Stack) Top() rune {
	if !s.IsEmpty() {
		return s.stack[len(s.stack)-1]
	} else {
		return -1
	}
}

func main() {
	infix := ""
	fmt.Scan(&infix)

	opStack := Stack{}
	postfix := ""

	for _, char := range infix {
		if char == '+' || char == '-' || char == '*' || char == '/' {
			if preced(char) > preced(opStack.Top()) {
				opStack.Push(char)
			} else {
				for preced(char) <= preced(opStack.Top()) {
					postfix += string(opStack.Top())
					opStack.Pop()
				}
				opStack.Push(char)
			}
		} else if char == '(' {
			opStack.Push(char)
		} else if char == ')' {
			for opStack.Top() != '(' {
				top := opStack.Top()
				postfix += string(top)
				opStack.Pop()
			}
			opStack.Pop()
		} else {
			postfix += string(char)
		}
	}
	for !opStack.IsEmpty() {
		postfix += string(opStack.Top())
		opStack.Pop()
	}

	fmt.Print(postfix)
}

// 우선 순위 판별 함수
func preced(v rune) int {
	if v == '+' || v == '-' {
		return 1
	} else if v == '*' || v == '/' {
		return 2
	} else {
		return 0
	}
}

💡 풀이

중위 표기법을 후위 표기법으로 바꾸는 방법을 알면 이 문제는 다 푼 것.

1. 연산자를 저장할 Stack opStack을 만든다.
2. infix를 왼쪽부터 오른쪽으로 탐색한다.
   • 문자가 피연산자(A, B, C…)라면 postfix 에 추가한다.
   • 문자가 ‘(’ 라면에 opStack에 추가한다.
   • 문자가 ‘)’라면 opStack에 있는 모든 연산자를 ‘(’를 만날 때까지 postfix에 추가하고 ‘(’를 제거한다.
   • 문자가 연산자(’+’, ‘-’, ‘*’, ‘/’)라면
     • 만약 그 문자가 opStack의 top 요소보다 우선 순위가 높으면 opStack에 추가한다.
     • 우선 순위가 낮으면 문자보다 우선 순위가 높거나 같은 요소들을 모두 postfix에 추가하고 문자를 opStack에 추가한다.
3. 탐색을 마친 후 opStack에 남아있는 모든 요소를 postfix에 추가한다.

🔁 삽질

• 문제를 보면 대강 풀이 방법이 감이 오는 문제가 있고 아닌 문제가 있는데 이건 후자의 문제라서 바로 풀이 알고리즘만 구현했다.
• 문자가 연산자 일 때, 연산자의 우선 순위를 고려하지 않아서 잠깐 헤맸었다,

📖 새롭게 배운 내용

• infix→ postfix 알고리즘
• go의 rune type
  go만의 독특한 type으로 string의 각 문자(UTF-8)를 다루기 위한 type이다. int32랑 동등하다.
  ASCII를 다루는 type은 byte로 uint8과 동등하다.
  

💫 헷갈리는 부분

❌

📚 참고 자료

go - rune 타입 (한글, 유니코드, UTF-8)

4.9. Infix, Prefix and Postfix Expressions - Problem Solving with Algorithms and Data Structures

Convert Infix to Postfix Expression