#4. 수식을 후위식으로 변환하고 계산하기

문제

main문에서 주어진 수식을 후위식으로 변환 후 변환 된 수식을 후위계산하여 값을 출력하시오

풀이

수식을 후위식으로 변환하는 함수부터 진행하기 때문에 스택의 요소는 char형 입니다.

일반적인 후위변환식을 작성하고, push,pop,peek등의 스택의 기본적인 연산 함수를 그대로 이용하여 후위계산을 하려면

스택의 요소를 int형으로 바꿔주어야하는데(숫자가 스택에 push되므로) 

스택에 push할 때 char형을 int형으로 형변환하여  push하는 것 외에 일반적인 수식계산 함수와 다를 게 없습니다.

코드

// C program to convert infix expression to postfix  
#pragma warning(disable:4996)
#include <stdio.h> 
#include <string.h> 
#include <stdlib.h> 
 
// Stack type 
struct Stack
{
    int top;
    unsigned capacity;
    int* array;
};
 
// Stack Operations 
struct Stack* createStack(unsigned capacity)
{
    struct Stack* stack = (struct Stack*) malloc(sizeof(struct Stack));
 
    if (!stack)
        return NULL;
 
    stack->top = -1;
    stack->capacity = capacity;
 
    stack->array = (int*)malloc(stack->capacity * sizeof(int));
 
    return stack;
}
int isEmpty(struct Stack* stack)
{
    return stack->top == -1;
}
char peek(struct Stack* stack)
{
    return stack->array[stack->top];
}
char pop(struct Stack* stack)
{
    if (!isEmpty(stack))
        return stack->array[stack->top--];
    return '$';
}
void push(struct Stack* stack, char op)
{
    stack->array[++stack->top] = op;
}
 
 
// A utility function to check if the given character is operand 
int isOperand(char ch)
{
  
    return (ch >= '0' && ch <= '9');
}
 
// A utility function to return precedence of a given operator 
// Higher returned value means higher precedence 
int Prec(char ch)
{
    switch (ch)
    {
    case '+':
    case '-':
        return 1;
 
    case '*':
    case '/':
        return 2;
 
    case '^':
        return 3;
    }
    return -1;
}
 
 
// The main function that converts given infix expression 
// to postfix expression.  
void infixToPostfix(char* exp)
{
    int i, k;
 
    // Create a stack of capacity equal to expression size  
    struct Stack* stack = createStack(strlen(exp));
    if (!stack) // See if stack was created successfully  
        return;//오류 
 
    for (i = 0, k = -1; exp[i]; ++i)
    {
        // If the scanned character is an operand, add it to output. 
        if (isOperand(exp[i]))
            exp[++k] = exp[i];
 
        // If the scanned character is an ‘(‘, push it to the stack. 
        else if (exp[i] == '(')
            push(stack, exp[i]);
 
        // If the scanned character is an ‘)’, pop and output from the stack  
        // until an ‘(‘ is encountered. 
        else if (exp[i] == ')')
        {
            while (!isEmpty(stack) && peek(stack) != '(')
                exp[++k] = pop(stack);
            if (!isEmpty(stack) && peek(stack) != '(')
                return; // invalid expression         //오류      
            else
                pop(stack);
        }
        else // an operator is encountered 
        {
            while (!isEmpty(stack) && Prec(exp[i]) <= Prec(peek(stack)))
                exp[++k] = pop(stack);
            push(stack, exp[i]);
        }
 
    }
 
    // pop all the operators from the stack 
    while (!isEmpty(stack))
        exp[++k] = pop(stack);
 
    exp[++k] = '\0';
    printf("%s\n", exp);
    
 
}
int eval(char* exp)
{
    struct Stack* stack = createStack(strlen(exp));
    if (!stack) // See if stack was created successfully  
        exit(1);
    int op1, op2, n;
    char ch;
    n = strlen(exp);
    for (int i = 0; i < n; i++)
    {
        ch = exp[i];
        //숫자일 떄
        if (ch != '+' && ch != '-' && ch != '*' && ch != '/')
            push(stack, ch-'0');
        else
        {
            op2 = pop(stack);
            op1 = pop(stack);
            switch (ch)
            {
            case '+': push(stack, op1 +op2); break;
            case '-':push(stack, op1 -op2); break;
            case '*':push(stack, op1 *op2); break;
            case '/':push(stack, op1 /op2); break;
            }
        }
    }
    return pop(stack);
}
// Driver program to test above functions 
int main()
{
    int result;
    char exp[] = "3+4/4*3-2*2";
    infixToPostfix(exp);
    
    result=eval(exp);
    printf("결과값은 %d입니다.\n", result);
    return 0;
}
 
 

결과