05-03 스택을 응용한 사칙 연산기1

 

아래의 상기 내용은

"이것이 자료구조+알고리즘이다. With C언어"의 도서 내용과 인터넷의 내용을 실습 및 정리한 글입니다.

1.스택으로 만드는 사칙연산기

 1)개요

-우리는 일상적으로 사칙연산을 하는데 연산자가 피연산자 중간에 위치하는 중위표기식을 쓴다.

 

-위의 식을 우리가 사칙연산을 하는데 괄호 안의 식 그리고 나눗셈 및 곱셈을 먼저 풀게 될 것이다.

 이것이 우리에겐 익숙한 관습을 익히도록 배워왔다.

-하지만 컴퓨터는 괄호나 곱셈,나눗셈의 순서를 이런 관습이 없고 이 문제를 해결하는 알고리즘을

 제공해야 식을 풀 수 있다. 

-우리가 사용하는 순서에 상관없이 괄호나 곱셈과 나눗셈에 따라 식의 우선 순위가 달라지는 중위표기식은 컴퓨터에게는 알맞는 방식이 아니다.

 -그래서 컴퓨터는 주로 후위표기식이 이용된다.

2.여러가지 수식의 표기법

 1)전위 표기법

  -연산자가 피연산자 앞에 위치한 표기식

 2)중위 표기법

  -연산자가 피연산자 사이에 위치한 표기식

 3)후위 표기법

  -연산자가 피연산자 뒤에 위치한 표기식.

3.후위표기식을 계산하는 알고리즘 규칙 및 순서도

 1) 식의 왼쪽부터 읽되 그 요소가 피연산자 라면 스택에 삽입

  -아래의 그림은 왼쪽부터 순서대로 1,3,2의 피연산자를 스택에 삽입됨

 2)연산자가 나타나면 스택에서 피연산자를 꺼내 연산을 실행하고 그 결과를 다시 스택에 삽입

  - (*)곱셈 연산자가 나왔을 때 2와3을 계산하고 그 결과 6을 삽입됨.

 3)알고리즘의 순서도

 

4)알고리즘 구현

 

 

4.중위 표기식에서 후위표기식으로 바꾸는 알고리즘

 1)개요

 -컴퓨터가 후위표기식을 사용하는 것이 더 좋을지 모르지만 사람에게는 중위표기식이 더 익숙하고 편하다.

 -그래서 우리는 중위표기식을 입력하여  컴퓨터가 후위표기식으로 바꿔 사용하면 된다. 그리고 그러기 위해

  별도의 알고리즘이 필요하다.

  2)동작과정

 

 

    

 

3)알고리즘 구현