스택 - 계산기1

1. 계산기 1

• 문자열로 된 계산식이 주어질 때, 스택을 이용하여 이 계식의 값을 계산할 수 있습니다.
• 문자열 수식 계산의 일반적 방법
  • step1. 중위 표기법의 수식을 후위 표기법으로 변경합니다. (스택 이용)
  • step2. 후위 표기법의 수식을 스택을 이용하여 계산합니다.

---

2. step1. 중위표기식의 후위표기식 변환 방법 1

• 수식의 각 연산자에 대해서 우선순위에 따라 괄호를 사용하여 다시 표현합니다.
• 각 연산자를 그에 대응하는 오른쪽 괄호의 뒤로 이동시킵니다.
• 괄호를 제거합니다.

---

3. step1. 중위 표기법에서 후위 표기법으로의 변환 알고리즘(스택 이용) 2

• 입력받은 중위 표기식에서 토큰을 읽습니다.
• 토큰이 피연산자이면 토큰을 출력합니다.
• 토큰이 연산자(괄호 포함) 일 때, 이 토큰이 스택의 top에 저장되어 있는 연산자보다 우선순위가 높으면 스택에 push 하고, 그렇지 않다면 스택 top의 연산자의 우선순위가 토큰의 우선순위보다 작을 때까지 스택에서 pop 한 후 토큰의 연산자를 psuh 합니다. 만약 top에 연산자가 없으면 push 합니다.
• 토큰이 오른쪽 괄호 ')'이면 스택 top에 왼쪽 괄호 '('가 올 때까지 스택에 pop 연산을 수행하고 pop 한 연산자를 출력합니다. 왼쪽 괄호를 만나면 pop만 하고 출력하지는 않습니다.
• 중위 표기식에 더 읽을 것이 없다면 중지하고, 더 읽을 것이 있다면 1부터 다시 반복합니다.
• 스택에 남아 있는 연산자를 모두 pop 하여 출력합니다. (스택 밖의 왼쪽 괄호는 우선순위가 가장 높으며, 스택 안의 왼쪽 괄호는 우선 순위가 가장 낮습니다.)

---

---

---

---

---

---

---

---

---

---

---

---

---

---

 

---

---

---

연습문제