컴퓨터의 수치연산원리, Infix to Postfix에 대한 이해

개요

안녕하세요.

중위 표기법(infix)으로 표현된 수식을 후위 표기법(postfix)로 바꾸는 C++ 계산기입니다.

 

1. 문자열로 중위표기법 입력 ( A-Z, a-z, 0~9,+,-,*,/,^,(,) )

 

2. 피연산자 (A-Z, a-z, 0~9) 는 후위식 문자열에 저장

 

3. 열리는 괄호 '(' 는 Stack에 저장

 

4. 닫기는 괄호 ')' 만나면 다음 '(' 만나기 전까지 Stack Pop 수행, 후위식 문자열에 저장

 

5. 연산자는 Stack에 추가 우선순위가 높은 연산자는 Stack Pop 수행, 후위식 문자열에 저장

개발 환경

• C++17, Qt Creator 9.0.1, MinGW 11.2.0 64bit
  

• Windows 11 Pro

 

calc.h

#ifndef CALC_H
#define CALC_H

#include <string>

class Calc
{
public:
    Calc(const std::string& exp);
    ~Calc();

private:
    const unsigned int MAX;   
    std::string infix;

    int priority(char c);

 public:
    std::string infixToPostfix();
    int calcPostfix(const std::string& exp);
};

#endif // CALC_H

 

calc.cpp

#include "calc.h"
#include <iostream>
#include <cstring>
#include <stack>
#include <cmath>
using namespace std;

Calc::Calc(const string& exp)
    : MAX(100), infix(exp)
{    
}

Calc::~Calc()
{
}

int Calc::priority(char c)
{
    if (c=='^')
        return 3;
    else if(c=='*' || c=='/')
        return 2;
    else if(c=='+' || c=='-')
        return 1;
    else
        return -1;
}

string Calc::infixToPostfix()
{
    string postfix;
    stack<char> st;

    for(size_t i=0;i<infix.length();i++)
    {
        char c = infix[i];

        if ( (c>='A' && c<='Z') || (c>='a' && c<='z') || (c>='0' && c<='9') )
            postfix += c;
        else if(c=='(')
            st.push('(');
        else if(c==')')
        {
            while ( st.top()!='(' )
            {
                postfix += st.top();
                st.pop();
            }
            st.pop();
        }
        else
        {
            while ( !st.empty() && priority(c) <= priority(st.top()) )
            {
                postfix += st.top();
                st.pop();
            }
            st.push(c);
        }
    }

    while (!st.empty())
    {
        postfix += st.top();
        st.pop();
    }
    return postfix;
}

int Calc::calcPostfix(const string& exp)
{
    stack<int> st;

    for (size_t i=0; i<exp.length(); i++)
    {
        char c = exp[i];

        if (c>='0' && c<='9')
            st.push( c - 0x30 );
        else if( (c>='A' && c<='Z') || (c>='a' and c<='z') )
        {
            cout << "A-Z, a-z expression can not be calculated." << '\n';
            break;
        }
        else
        {
            int a = st.top();
            st.pop();
            int b= st.top();
            st.pop();

            switch(c)
            {
            case '+':
                st.push(b+a); break;
            case '-':
                st.push(b-a); break;
            case '*':
                st.push(b*a); break;
            case '/':
                st.push(b/a); break;
            case '^':
                st.push(pow(b,a)); break;
            }
        }
    }
    return st.top();
}

main.cpp

#include <iostream>
#include <string>
#include "calc.h"
using namespace std;

int main()
{
    // 8/2^3+2*3-5*1
    string str;
    cout << "Input Math Expression [A-Z, a-z, 0~9,+,-,*,/,^,(,)] : ";
    cin >> str;

    Calc c(str);

    string postfix = c.infixToPostfix();
    cout <<  postfix << '\n';
    cout << c.calcPostfix(postfix) << '\n';
    return 0;
}

 

모든 코드가 이해된다면 Template을 시도해 볼 차례입니다.

감사합니다.