들어가기 앞서
스택을 이용하여 계산기 예제 프로그램을 만들건데요.
일반적으로 사용하는 계산기는, 공학 계산기 및 인터넷 계산기가 아닌 이상 괄호를 처리할 수 없죠?
또한 식이 안보여서 연산기호 한번 잘못하면 짜증나게 됩니다.
이러한 문제를 해결하기 위해 오늘은 스텍을 이용하여 계산기를 만들겁니다.
계산기를 만들기 전에 괄호와 연산 기호 우선순위를 고려하기 위하여 postfix 즉 후위 표기법을 사용하려 해요.
따라서 개념을 찬찬히 보고 익혀 가보도록 하겠습니다.
스텍에 대한 개념은 이전 게시물들을 보고 와주세요.
스택(Stack), c언어 구현 코드, 연결 리스트 기반 스택, 자료구조
들어가기 앞서 이전 게시물은, 스택을 배열 기반으로 구성해 봤습니다.이전 배열 기반으로 했을 때 단점은 capacity라는 건데요.즉 용량을 넘어서는 안된다는 점! 따라서 용량에 구애받지 않는
8ehrmin.tistory.com
스택(Stack), c언어 구현 코드, 배열 기반 스택, 자료구조
들어가기 앞서 이제 리스트들을 거쳐서 Stack으로 왔어요.스택은 리스트보다 이해가 잘 될 것이라고 생각합니다. 노드를 포인터를 이용하여 연결하는 것이 기억안난다면? 혹은 기초적인 것이
8ehrmin.tistory.com
후위 표기법(postfix)
대다수가 계산 식을 세울 때 다음과 같이 작성합니다.
중위 표기법(infix) : 산술 및 논리학 공식과 문장에서 일반적으로 사용되는 표기법 (위키백과)
1+2+3
이렇게 연산 기호가 수 안에 같이 존재하는데요.
이를 중위 표기법이라고 합니다.
그럼 후위는 뭘까요?
후위 표기법(postfix) : 연산자를 연산 대상의 뒤에 쓰는 연산 표기법 (위키백과)
12+3+
연산 대상을 기준으로, 연산자를 뒤에 작성하면 표기법입니다.
그럼 어떻게 "1+2+3"이 "12+3+"이 되었을까요?
바로 보이지 않는 괄호 뒤로 연산자가 이동했기 때문입니다.
왼쪽부터 오른쪽으로 계산하는 것이 원칙이지만, 연산 기호와 같이 우선순위를 따질 수 있는 것과 같습니다.
따라서 괄호 내에 있는 연산자를 괄호 밖으로 옮겨주면 되는 것 입니다.
하지만 움직인 연산자는 고집으로 인하여 움직이지 않으니, 옮겨졌다면 고정하여 두세요.
괄호로 묶기
그럼 우선순위가 있는 연산자를 예로 익숙해져 보겠습니다.
사칙연산이 한번에 나오니 보기 싫어졌습니다.
이제 우선순위 대로 묶어보도록 하겠습니다.
1. 기본 수식 입니다.
2. 곱하기와 나누기 연산자는 더하기와 빼기보다 우선순위가 높기 때문에, 먼저 묶어줍니다.
3. 이제 동일한 우선순위로 남았기 때문에, 기존처럼 왼쪽부터 오른쪽으로 한 항씩 괄호로 묶어줍니다.
4. 3번과 동일하게 보면 됩니다.
연산자 빼기
이제 괄호내에 있는 연산자를 괄호 밖으로 꺼내면 후위 표기법 입니다.
이렇게 꺼내면 되는거죠?
혹시 이것도 이해를 못하셨다면, 차례대로 보겠습니다.
우선순위가 높은 연산자를 괄호 밖으로 빼면서, 괄호도 없애주어야 합니다.
순차적으로 보겠습니다.
1. 기본 식에 우선순위를 괄호로 표현한 식 입니다.
1.1. 우선순위가 가장 높은 곱하기와 나누기를 각각 괄호 밖으로 꺼내면서, 괄호를 지웁니다.
2. 그다음 우선순위가 가장 높은(가장 왼쪽에 있는) 더하기 연산자를 괄호 밖으로 꺼내주면서, 괄호를 지웁니다.
3. 마지막으로 남아있는 빼기를 괄호 밖으로 꺼내주면서, 괄호를 지웁니다.
4. 완성
이렇게 후위 표기법으로 만들어 줬습니다.
후위 표기법(postfix) 스택 기반 계산
그러면 계산은 어떻게 이루어질까요?
이전 식을 그대로 가져오겠습니다.
1 + 2 * 3 - 4 / 5
= 1 + ( 6 ) - ( 4 / 5 )
= 7 - ( 0.8 )
= 6.2
계산을 수행하는데에 있어 아무런 문제가 없어 보입니다.
이전 중위 표기법인 식을 후위 표기법인 식으로 변환해 보겠습니다.
1 2 3 * + 4 5 / -
중위 표기법과 같이 왼쪽에서 부터 오른쪽으로 계산을 이어갈 것 입니다.
기호가 보인다면 기호의 바로 왼쪽 2개의 피연산자들을 묶어보고 계산해 보겠습니다.
= 1 2 3 * + 4 5 / -
= 1 ( 2 3 * ) + 4 5 / -
= 1 6 + 4 5 / -
= ( 1 6 + ) 4 5 / -
= 7 4 5 / -
= 7 (4 5 / ) -
= 7 0.8 -
= (7 0.8 - )
= 6.2
중위 표기법으로 작성된 수식과 계산 값이 다르지 않습니다.
그럼 스택으로 어떻게 표현할 수 있을까요?
char postfix[] = "1 2 3 * + 4 5 / -"; // 공백은 없다고 치셈
다음과 같이 후위 표기법으로 변환된 배열이 있습니다.
아까 말 한 것 처럼 계산을 위해 두개의 조건을 두겠습니다.
1. 왼쪽에서 오른쪽 방향으로 순차적이게 스택에 저장 .
2. 연산 기호를 만날 경우, 두개의 피연산자를 POP하여 계산 후 스택에 저장
이제 하나씩 스택에 POP과 PUSH를 해가며 계산을 해 보겠습니다.
후위 표기법으로 작성된 수식을 스택을 이용하여 계산할 수 있습니다.
그럼 중위 표기법에서 후위 표기법으로 변환되는 코드는 어떤 원리로 이루어 질까요?
중위 표기법(infix) -> 후위 표기법(postpix) 스택 기반 변환
후위 표기법으로 변환하기 위하여 중위 표기법인 수식을 굳이 모두 스택에 넣을 필요가 없어보입니다.
물론 넣어도 상관은 없지만, 굳이 전체적으로 동적 메모리를 할당하고 해제 해 가면서 까지 할 작업이 아니기 때문입니다.
연산 기호의 우선순위 파악을 위하여 연산 기호만 스택을 활용 해 보도록 합시다.
우선순위 파악을 위한 조건으로,
1. 새롭게 발견된 연산 기호가 스택 TOP에 있는 연산 기호보다 우선순위가 낮을 경우, 스택을 POP한다.
2. 새롭게 발견된 연산 기호가 스택 TOP에 있는 연산 기호보다 우선순위가 높을 경우, new 연산 기호를 PUSH한다.
일단 중위 표기법인 수식을 사용자에게 받을 것 입니다.
이 수식에는 숫자와 연산자가 있을 것 입니다.
char infixExpression[100] = "1+2*3+4/5";
char postfixExpression[100] // infix를 후위 표기법으로 변환하여 담을 배열
그럼 인덱스를 생각 해 보겠습니다.
이제 순차적으로 infix 배열에서 postfix 배열로 옮겨볼까요?
숫자는 굳이 스택에 넣을 필요가 없다고 했죠?
배열에 바로 복사해 줍시다.
연산자가 나왔네요.
스택에 PUSH해 줍시다.
그냥 숫자니까 복사해줍시다.
새롭게 발견된 연산 기호(*)가 스택 TOP에 있는 연산 기호(+)보다 우선순위가 높았기 때문에, PUSH를 해줍시다.
그냥 숫자니까 복사해줍시다.
새롭게 발견된 연산 기호(+)가 스택 TOP에 있는 연산 기호(*)보다 우선순위가 낮을 경우, 스택을 POP해야 하죠?
POP해줍시다.
POP 함돠,
POP 이후, 스택에 발견했던 연산 기호를 PUSH해 줍니다.
그냥 숫자니까 복사해줍시다.
새롭게 발견된 연산 기호(/)가 스택 TOP에 있는 연산 기호(+)보다 우선순위가 높았기 때문에, PUSH를 해줍시다.
그냥 숫자니까 복사해줍시다.
이제 '\0'를 마주했다면, 스텍에 있는 모든 연산 기호를 POP 해주면 됩니다.
결과가 잘 나왔는지 확인합시다.
결과 : 1 2 3 * + 4 5 / +
이전 수기로 했던 수식들
결과 : 1 2 3 * + 4 5 / +
// -를 +로 대체했습니다.
잘 나왔네요 이제 코드로 볼까요?
중위 표기법(infix) -> 후위 표기법(postpix) 스택 기반 변환 코드
데이크스트라(Dijkstra) 알고리즘
먼저 노드와 스텍 관련된 코드는 이전 게시물에서 소개한바 있기 때문에, 모르면 보고와주세요.
스택(Stack), c언어 구현 코드, 연결 리스트 기반 스택, 자료구조
들어가기 앞서 이전 게시물은, 스택을 배열 기반으로 구성해 봤습니다.이전 배열 기반으로 했을 때 단점은 capacity라는 건데요.즉 용량을 넘어서는 안된다는 점! 따라서 용량에 구애받지 않는
8ehrmin.tistory.com
일단 숫자가 한자리만 있으면 좋겠지만, 10이있고 100이 있습니다.
따라서 한자리 숫자인지 두자리 숫자인지 구분하기 위해 그리고 문자열로 오는 문자들이 숫자인지 연산 기호인지 구분하기 위하여 다음과 같은 코드를 작성합니다.
typedef enum // 연산 기호 구분
{
LEFT_PARENT = '(',
RIGHT_PARENT = ')',
PLUS = '+',
MINUS = '-',
MULTILY = '*',
DIVIDE = '/',
SPACE = ' ',
OPERAND
} Symbol;
//문자로 오는 숫자들 구분
char number[] = { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', '.' };
int numberLength = sizeof(number);
// number배열에 있는지 확인하고 숫자인지 판별
// isdigit 기능과 동일
int isNumber(char c)
{
int i = 0;
for (i = 0; i < numberLength; i++)
{
if (c == number[i]) return 1;
}
return 0;
}
unsigned int getNextToken(char* expression, char* token, int* type)
{
unsigned int i = 0;
for (i = 0; 0 != expression[i]; i++)
{
token[i] = expression[i];
if (isNumber(expression[i]) == 1)
{
*type = OPERAND;
if (isNumber(expression[i + 1]) != 1) break; //그 담이 숫자가 아니면 break
}
else
{
*type = expression[i];
break;
}
}
token[++i] = '\0'; //수식은 한 항씩 끊김
return i;
}
getNextToken을 보겠습니다.
들어온 매개변수들은 각각,
expression: infix로 표기된 수식
token : 숫자 인지 기호인지 판별 후 기호 혹은 한 항으로만 리턴을 받을 문자열 포인터
type : 연산 기호와 수식 구분 타입 enum symbol
unsigned int getNextToken(char* expression, char* token, int* type)
{ . . . }
반복문을 보겠습니다.
수식을 순차적으로 받고있죠?
조건문을 보겠습니다.
만약에 들어온 수식의 i번째 인덱스가 숫자인 경우,
type을 operand로 변경해라.
또한 다음 인덱스가 연산 기호인 경우, 반복문을 멈춰라.
즉 74+3이라면,
i = 0 : index가 0일 때 숫자 7이며 다음 index는 4이기 때문에 반복 i++
i = 1 : index가 1일 때 숫자 4이며 다음 index는 +이기 때문에 break;
탈출하면서 i는 1입니다.
후에 token[++i] = '\0' 즉 문자열 끝이라는 것을 알리면서 74+3이 74만 남게 됩니다.
또한 i는 ++i가 되면서 2가 되는 거죠.
token은 포인터이기 때문에 보내지고, 74까지의 포지션 i(2)가 리턴되면서
다시 getNextToen에 오게되면 수식 " 74+3 "의 +부터 즉 index 2 부터 시작하게 됩니다.
unsigned int i = 0;
for (i = 0; 0 != expression[i]; i++)
{
token[i] = expression[i];
if (isNumber(expression[i]) == 1)
{
*type = OPERAND;
if (isNumber(expression[i + 1]) != 1) break; //그 담이 숫자가 아니면 break
}
else
{
*type = expression[i];
break;
}
}
token[++i] = '\0'; //수식은 한 항씩 끊김
return i;이제 토큰으로 부셔주었으니, 다음은 연산 기호들의 우선순위를 파악해야 합니다.
또한 괄호의 역할도 파악해야하죠.
어떤 연산기호가 있던, 괄호가 있으면 가장 안쪽의 괄호부터 풀어주어야 합니다.
그렇다는 말은 괄호가 우선순위가 가장 높다는 말이겠죠.
일반적으로 후위 표기법을 사용할 때 괄호를 제거하고 작성합니다.
연산 기호의 위치가 괄호의 역할을 하기 때문이죠.
1 + ( 2 + ( 3 + 4 ) )
하지만 중위 표기법에서 후위 표기법으로 변환하기 위해서는 괄호들이 많을 때 어떻게 해야하는지 생각해 보아야 합니다.
과정은 두개로 볼 수 있습니다.
스택에서 괄호
1. ')' 괄호가 나왔을 때, '(' 괄호가 나올 때 까지 POP 한다.
2. 연산 기호와 '(' 괄호의 우선순위를 구분한다.
1번 같은 경우는, 무조건 적으로 ( 왼쪽이 있어야 ) 오른쪽이 있기 때문에, 계산을 위해서는 왼쪽이 나올 때 까지 POP한 후 postfix 배열에 복사하면 됩니다.
2번 같은 경우는, 이전 스택 조건을 확인 해 볼까요?
스택 조건
1. 새롭게 발견된 연산 기호가 스택 TOP에 있는 연산 기호보다 우선순위가 낮을 경우, 스택을 POP한다.
2. 새롭게 발견된 연산 기호가 스택 TOP에 있는 연산 기호보다 우선순위가 높을 경우, new 연산 기호를 PUSH한다.
해당 조건을 따르면서 우선순위를 구분해야 합니다.
( 왼쪽 괄호가 나왔다고 한들, 스텍에 있는 모든 스택을 POP하면 안되기 때문이죠.
따라서
1. 왼쪽 괄호가 발견되었을 때 스택에 ( 왼쪽 괄호가 있다면, PUSH를 해주어야 합니다.
2. 오른쪽 괄호가 아닌 경우, 왼쪽 괄호까지 POP을 하지 않는다.
예를들면
1 + ( 2 + ( 3 + 4 ) )
이 상황에서 첫번 째 1을 복사한 후의 상황을 봅시다.
이 다음은 왼쪽 괄호와 만나게 될 것입니다.
이 때 괄호는 스택에 들어가는게 정답인 것을 알 수 있습니다.
왜냐하면 현 수식에서 1 옆에있는 +는 우선순위가 가장 낮기에 지금 당장 계산하면 안되잖아요.
따라서 새롭게 발견된 연산 기호('(')가 스택 TOP에 있는 연산 기호(+)보다 우선순위가 높을 경우, new 연산 기호를 PUSH해야하기 때문에 '(' > ' +' , 왼쪽 괄호 ( 의 우선순위는 가장 높을 것 입니다.
그럼 다음 문제를 볼까요?
이 왼쪽 괄호가 stack에 있는 상황에서, 또 만났을 때, 어떻게 해야할까요?
당연히 해당 왼쪽 괄호도 스텍에 들어가야 합니다.
아직 오른쪽 괄호를 만나보지도 못한 상황이기 때문이죠.
그럼 다시 생각해 봅시다.
새롭게 발견된 연산 기호('(')가 스택 TOP에 있는 연산 기호('(')보다 우선순위가 높을 경우, new 연산 기호를 PUSH해야 하기 때문에, stack에 있는 괄호의 우선순위를 낮추어야 합니다.
따라서 다음과 같은 코드를 작성하면 해결됩니다.
int getPriority(char oper, int inStack)
{
int priority = -1;
switch (oper)
{
case LEFT_PARENT:
if (inStack) priority = 0;
else priority = 3;
break;
case MULTILY:
case DIVIDE:
priority = 2;
break;
case PLUS:
case MINUS:
priority = 1;
break;
}
return priority;
}
매개변수를 확인하면,
oper : 연산자
instack : stack에 있는 왼쪽 괄호인지 확인하기 위한 코드
코드만 봤을 때, 괄호를 제외한 나머지 연산자들은 inStack 정수를 사용하지 않습니다.
따라서 해당 코드를 이용하여 스택에 있는지 없는지에 따라 왼쪽 괄호의 우선순위를 조정할 수 있습니다.
이제 드디어 후위 표기법으로 변환할 수 있겠네요.
int isPrior(char operInStack, char operInToken)
{
return(getPriority(operInStack, 1) < getPriority(operInToken, 0));
}
void getPostfix(char* infixExpression, char* postfixExpression)
{
likedListStack* stack;
char token[32];
int type = -1;
unsigned int position = 0;
unsigned int length = strlen(infixExpression);
createStackLIS(&stack);
while (position < length)
{
position += getNextToken(&infixExpression[position], token, &type); //식 인덱스
if (type == OPERAND)
{
strcat(postfixExpression, token);
strcat(postfixExpression, " ");
}
else if (type == RIGHT_PARENT)
{
while (!isEmptyLIS(stack))
{
Node* popped = popNodeLIS(stack);
if (popped->data[0] == LEFT_PARENT)
{
destroyNodeLIS(popped);
break;
}
else
{
strcat(postfixExpression, popped->data);
destroyNodeLIS(popped);
}
}
}
else
{
while (!isEmptyLIS(stack) && !isPrior(getTopLis(stack)->data[0], token[0]))
{
Node* popped = popNodeLIS(stack);
if (popped->data[0] != LEFT_PARENT)
{
strcat(postfixExpression, popped->data);
}
destroyNodeLIS(popped);
}
pushNodeLIS(stack, createNodeLIS(token));
}
}
while (!isEmptyLIS(stack))
{
Node* popped = popNodeLIS(stack);
if (popped->data[0] != LEFT_PARENT) strcat(postfixExpression, popped->data);
destroyNodeLIS(popped);
}
destroyStackLIS(stack);
}
이제 매개변수는 다음과 같습니다.
char* infixExpression : 입력받은 중위 표기법 수식 배열
char* postfixExpression : 변환하여 담기 위한 후위 표기법 수식 배열
해당 함수에서 사용하는 지역변수를 보겠습니다.
likedListStack stack : 연산 기호를 쌓을 스택입니다.
char token[] : 수식 중 하나의 항을 담을 배열입니다.
int type : 연산 기호 및 수식 구분을 위한 정수형 변수입니다.
unsigned int position : 반복문에서 사용하기 위한 infixExpression의 현재 인덱스 입니다.
unsigned int length : infixExpression의 크기입니다.
void getPostfix(char* infixExpression, char* postfixExpression)
{
likedListStack* stack;
char token[32];
int type = -1;
unsigned int position = 0;
unsigned int length = strlen(infixExpression);
.
.
.
}
이전에 설명한 token함수를 통해 항(token)과 항의 type을 받을 수 있습니다.
해당 값들을 이용한 조건문을 확인합시다.
if : 연산자 즉 숫자면 postfix 배열에 cat 복사합니다.
else if : 오른쪽 괄호라면, 왼쪽 괄호가 나올때 까지 연산 기호(pop)와 숫자를 posfix배열에 복사합니다. 반대로 왼쪽이라면 소멸하며 끝입니다.
else : 연산 기호이거나 왼쪽 괄호라면,
스택 TOP에 있는 연산 기호보다 현 token의 우선순위가 높을 때 까지, 스택을 POP합니다.
아니라면 현 token을 push합니다.
while (position < length)
{
position += getNextToken(&infixExpression[position], token, &type); //식 인덱스
if (type == OPERAND)
{
strcat(postfixExpression, token);
strcat(postfixExpression, " ");
}
else if (type == RIGHT_PARENT)
{
while (!isEmptyLIS(stack))
{
Node* popped = popNodeLIS(stack);
if (popped->data[0] == LEFT_PARENT)
{
destroyNodeLIS(popped);
break;
}
else
{
strcat(postfixExpression, popped->data);
destroyNodeLIS(popped);
}
}
}
else
{
while (!isEmptyLIS(stack) && !isPrior(getTopLis(stack)->data[0], token[0]))
{
Node* popped = popNodeLIS(stack);
if (popped->data[0] != LEFT_PARENT)
{
strcat(postfixExpression, popped->data);
}
destroyNodeLIS(popped);
}
pushNodeLIS(stack, createNodeLIS(token));
}
}배열의 모든 인덱스를 확인한 후,
연산 기호 스택이 비어있지 않은 경우에 pop을 해주어 배열에 복사해줍시다.
while (!isEmptyLIS(stack))
{
Node* popped = popNodeLIS(stack);
if (popped->data[0] != LEFT_PARENT) strcat(postfixExpression, popped->data);
destroyNodeLIS(popped);
}스택을 이용한 후위 표기법(postfix) 수식 계산
후위 표기법을 계산하는건 거의 맨 처음에 알려드렸는데요, 알려준 대로 행하면 됩니다. 한번 볼까요?
double calculate(char* postfixExpression)
{
likedListStack* stack;
Node* resultNode;
double result;
char token[32];
int type = -1;
unsigned int read = 0;
unsigned int length = strlen(postfixExpression);
createStackLIS(&stack);
while (read < length)
{
read += getNextToken(&postfixExpression[read], token, &type);
printf("read : %d\n", read);
if (type == SPACE) continue;
if (type == OPERAND)
{
Node* newNode = createNodeLIS(token);
pushNodeLIS(stack, newNode);
}
else
{
char resultString[32];
double operator1, operator2, tempResult;
Node* operatorNode;
operatorNode = popNodeLIS(stack);
operator2 = atof(operatorNode->data);
destroyNodeLIS(operatorNode);
operatorNode = popNodeLIS(stack);
operator1 = atof(operatorNode->data);
destroyNodeLIS(operatorNode);
switch (type)
{
case PLUS: tempResult = operator1 + operator2; break;
case MINUS: tempResult = operator1 - operator2; break;
case MULTILY: tempResult = operator1 * operator2; break;
case DIVIDE: tempResult = operator1 / operator2; break;
}
gcvt(tempResult, 10, resultString);
pushNodeLIS(stack, createNodeLIS(resultString));
}
}
resultNode = popNodeLIS(stack);
result = atof(resultNode->data);
destroyNodeLIS(resultNode);
destroyStackLIS(stack);
return result;
}매개 변수와 지역 변수는 이전에 설명한 것과 비슷하니 넘기겠습니다.
그럼 바로 반복문을 볼건데요,
이전에 설명한 token함수를 통해 항(token)과 항의 type을 받을 수 있습니다.
해당 값들을 이용한 조건문을 확인합시다.
if (type == OPERAND)
type이 수식이라면 일단 스택에 PUSH해라.
else
아니라면? 두개의 피연산자를 스택에서 꺼낸 후,
atof(아스키 to 실수)로 변환하여 두 피연산자를 계산해라.
계산 후 부동소수점으로 변환하여 스택에 넣어라.
후 반복을 하게 됩니다.
계산은 처음에 설명한 것과 동일하게 흘러갑니다.
연산자를 만나면 두개의 피연산자를 스택에서 POP하여 계산한다.
이게 끝입니다.
while (read < length)
{
read += getNextToken(&postfixExpression[read], token, &type);
printf("read : %d\n", read);
if (type == SPACE) continue;
if (type == OPERAND)
{
Node* newNode = createNodeLIS(token);
pushNodeLIS(stack, newNode);
}
else
{
char resultString[32];
double operator1, operator2, tempResult;
Node* operatorNode;
operatorNode = popNodeLIS(stack);
operator2 = atof(operatorNode->data);
destroyNodeLIS(operatorNode);
operatorNode = popNodeLIS(stack);
operator1 = atof(operatorNode->data);
destroyNodeLIS(operatorNode);
switch (type)
{
case PLUS: tempResult = operator1 + operator2; break;
case MINUS: tempResult = operator1 - operator2; break;
case MULTILY: tempResult = operator1 * operator2; break;
case DIVIDE: tempResult = operator1 / operator2; break;
}
gcvt(tempResult, 10, resultString);
pushNodeLIS(stack, createNodeLIS(resultString));
}
}
후위 표기법 스택 기반 계산 예제 프로그램
지금까지 배운 연산을 모두 활용할 수 있는 프로그램을 작성해 보겠습니다.
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#pragma warning(disable:4996)
typedef enum
{
LEFT_PARENT = '(',
RIGHT_PARENT = ')',
PLUS = '+',
MINUS = '-',
MULTILY = '*',
DIVIDE = '/',
SPACE = ' ',
OPERAND
} Symbol;
char number[] = { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', '.' };
int numberLength = sizeof(number);
typedef struct tagNode
{
char* data;
struct tagNode* nextNode;
}Node;
typedef struct tagLikedListStack
{
Node* list;
Node* top;
} likedListStack;
int isNumber(char c)
{
int i = 0;
for (i = 0; i < numberLength; i++)
{
if (c == number[i]) return 1;
}
return 0;
}
unsigned int getNextToken(char* expression, char* token, int* type)
{
unsigned int i = 0;
for (i = 0; 0 != expression[i]; i++)
{
token[i] = expression[i];
if (isNumber(expression[i]) == 1)
{
*type = OPERAND;
if (isNumber(expression[i + 1]) != 1) break;
}
else
{
*type = expression[i];
break;
}
}
token[++i] = '\0';
return i;
}
int getPriority2(char oper, int inStack)
{
int priority = -1;
switch (oper)
{
case LEFT_PARENT:
if (inStack) priority = 3;
else priority = 0;
break;
case MULTILY:
case DIVIDE:
priority = 1;
break;
case PLUS:
case MINUS:
priority = 2;
break;
}
return priority;
}
int getPriority(char oper, int inStack)
{
int priority = -1;
switch (oper)
{
case LEFT_PARENT:
if (inStack) priority = 0;
else priority = 3;
break;
case MULTILY:
case DIVIDE:
priority = 2;
break;
case PLUS:
case MINUS:
priority = 1;
break;
}
return priority;
}
int isPrior(char operInStack, char operInToken)
{
return(getPriority(operInStack, 1) < getPriority(operInToken, 0));
}
typedef int elementType;
Node* createNodeLIS(char* data)
{
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = (char*)malloc(sizeof(data) + 1);
strcpy(newNode->data, data);
newNode->nextNode = NULL;
return newNode;
}
void destroyNodeLIS(Node* node)
{
free(node->data);
free(node);
}
void createStackLIS(likedListStack** stack)
{
(*stack) = (likedListStack*)malloc(sizeof(likedListStack));
(*stack)->top = NULL;
(*stack)->list = NULL;
}
int isEmptyLIS(likedListStack* stack)
{
return stack->list == NULL;
}
Node* popNodeLIS(likedListStack* stack)
{
Node* popNode = stack->top;
Node* current = stack->list;
if (stack->top == stack->list)
{
stack->top = NULL;
stack->list = NULL;
}
else
{
while (current != NULL && current->nextNode != stack->top)
{
current = current->nextNode;
}
stack->top = current;
stack->top->nextNode = NULL;
}
return popNode;
}
void destroyStackLIS(likedListStack* stack)
{
while (!isEmptyLIS(stack))
{
Node* popNode = popNodeLIS(stack);
destroyNodeLIS(popNode);
}
free(stack);
}
void pushNodeLIS(likedListStack* stack, Node* node)
{
if (stack->list == NULL)
{
stack->list = node;
}
else
{
stack->top->nextNode = node;
}
stack->top = node;
}
int getSizeLIS(likedListStack* stack)
{
Node* curr = stack->list;
int size = 1;
while (curr != NULL && curr != stack->top)
{
size++;
curr = curr->nextNode;
}
return size;
}
Node* getTopLis(likedListStack* stack)
{
return stack->top;
}
void getPostfix(char* infixExpression, char* postfixExpression)
{
likedListStack* stack;
char token[32];
int type = -1;
unsigned int position = 0;
unsigned int length = strlen(infixExpression);
createStackLIS(&stack);
while (position < length)
{
position += getNextToken(&infixExpression[position], token, &type);
if (type == OPERAND)
{
strcat(postfixExpression, token);
strcat(postfixExpression, " ");
}
else if (type == RIGHT_PARENT)
{
while (!isEmptyLIS(stack))
{
Node* popped = popNodeLIS(stack);
if (popped->data[0] == LEFT_PARENT)
{
destroyNodeLIS(popped);
break;
}
else
{
strcat(postfixExpression, popped->data);
destroyNodeLIS(popped);
}
}
}
else
{
while (!isEmptyLIS(stack) && !isPrior(getTopLis(stack)->data[0], token[0]))
{
Node* popped = popNodeLIS(stack);
if (popped->data[0] != LEFT_PARENT)
{
strcat(postfixExpression, popped->data);
}
destroyNodeLIS(popped);
}
pushNodeLIS(stack, createNodeLIS(token));
}
}
while (!isEmptyLIS(stack))
{
Node* popped = popNodeLIS(stack);
if (popped->data[0] != LEFT_PARENT) strcat(postfixExpression, popped->data);
destroyNodeLIS(popped);
}
destroyStackLIS(stack);
}
double calculate(char* postfixExpression)
{
likedListStack* stack;
Node* resultNode;
double result;
char token[32];
int type = -1;
unsigned int read = 0;
unsigned int length = strlen(postfixExpression);
createStackLIS(&stack);
while (read < length)
{
read += getNextToken(&postfixExpression[read], token, &type);
if (type == SPACE) continue;
if (type == OPERAND)
{
Node* newNode = createNodeLIS(token);
pushNodeLIS(stack, newNode);
}
else
{
char resultString[32];
double operator1, operator2, tempResult;
Node* operatorNode;
operatorNode = popNodeLIS(stack);
operator2 = atof(operatorNode->data);
destroyNodeLIS(operatorNode);
operatorNode = popNodeLIS(stack);
operator1 = atof(operatorNode->data);
destroyNodeLIS(operatorNode);
switch (type)
{
case PLUS: tempResult = operator1 + operator2; break;
case MINUS: tempResult = operator1 - operator2; break;
case MULTILY: tempResult = operator1 * operator2; break;
case DIVIDE: tempResult = operator1 / operator2; break;
}
gcvt(tempResult, 10, resultString);
pushNodeLIS(stack, createNodeLIS(resultString));
}
}
resultNode = popNodeLIS(stack);
result = atof(resultNode->data);
destroyNodeLIS(resultNode);
destroyStackLIS(stack);
return result;
}
void calculatorLinkedListStackExe()
{
char infixExpression[100];
char postfixExpression[100];
double result = 0.0;
memset(infixExpression, 0, sizeof(infixExpression));
memset(postfixExpression, 0, sizeof(postfixExpression));
printf("입력 infixExpression : ");
scanf("%s", infixExpression);
getPostfix(infixExpression, postfixExpression);
printf("infix : %s\n", infixExpression);
printf("postfix : %s\n", postfixExpression);
result = calculate(postfixExpression);
printf("result : %f\n", result);
}
끝으로
후위 표기법을 계산하는건 얼마 걸리지 않지만, 변환하는 과정이 조금.. 복잡했다고 생각합니다.
하지만 이해만 하면 보지않아도 슥슥 할 수 있게 될 것 이라고 생각합니다.
틀린 점이 있다면 알려주세요
이해 안가는 부분이 있다면 장문으로 물어도 좋으니 언제든 물어봐주시길 바랍니다.
참고
이것이 자료구조 알고리즘이다 with C언어
'자료구조' 카테고리의 다른 글
| 스택(Stack), c언어 구현 코드, 연결 리스트 기반 스택, 자료구조 (0) | 2024.11.18 |
|---|---|
| 스택(Stack), c언어 구현 코드, 배열 기반 스택, 자료구조 (0) | 2024.11.18 |
| 환형 연결 리스트(Circular Licked List), 원형 연결 리스트, C언어 구현, 코드 부에궹ㄱ (1) | 2024.11.17 |
| 이중 연결 리스트(Double Linked List), C언어 구현, 코드 (0) | 2024.11.17 |
| 연결 리스트(Linked List), C언어 구현, 코드(너 ㅋ 이해하고 싶어?) (3) | 2024.11.15 |
