C,C++ 스택 계산기

중위연산은 연산자의 우선순위와 괄호의 유무로 좌에서 우로 문자열을 읽으면서 한번에 계산하기 어렵다.

이를 후위연산으로 스택을 이용하여 계산이 편리해진다.

스택을 이해하고 활용하는데 좋은 예제, 특히 괄호처리는 파서를 만드는데 좋은 예제라고 생각한다

#include 
#include 
#include 
#include 
#include
/********************
중의 후위연산 변환 및
연결리스트 스택 계산기
2014.07.03 by BBC1246
********************/
template
class LinkedList_Stack
{
public:

 struct list
 {
  list(){};
  list(T ele)
  {
   element = ele;
  }

  T element;
  list* next;

 };

 LinkedList_Stack()
 {
  head = NULL;
  tail = NULL;
  initstack();
 }
 ~LinkedList_Stack()
 {
  clear();
 }

 void initstack()
 {
  if (head != NULL)
   clear();
  head = new list();
  tail = new list();
  head->next = tail;
  tail->next = head;
 }

 T cehckTop()
 {
  if (head->next == tail)
   return 0;
  list* temp = head->next;
  T etemp = temp->element;
  return etemp;
 }
 T pop()
 {
  if (head->next == tail)
   return 0;

  list* tpop = head->next;
  head->next = tpop->next;
  T temp = tpop->element;
  delete tpop;
  return temp;

 }
 void push(T ele)
 {
  list* tpush = new list(ele);
  list* temp = head->next;
  head->next = tpush;
  tpush->next = temp;
 }
 void clear()
 {
  while (head->next != tail)
  {
   list* temp = head->next;
   head->next = temp->next;
   delete temp;
  }
  delete head;
  delete tail;
 }
 int isEmpty()
 {
  if (head->next == tail)
   return 1;
  else
   return 0;
 }

private:
 list* head;
 list* tail;

};

class calculator
{
public:

 calculator(char* formula)
 {

  size = 0;

  while (*formula++ != '\0')
   size++;
  size++;
  formula -= size;
  char* middle_formula = new char[size];

  memcpy(middle_formula, formula, size);

  change_Reverse_Poland(middle_formula);
 }
 //괄호 갯수 체크
 int checkBrackets(char* checkstr)
 {
  int c1 = 0;
  int c2 = 0;
  while (*checkstr)
  {
   if (*checkstr == '(') c1++;
   else if (*checkstr == ')') c2++;
   checkstr++;
  }
  if (c1 != c2)
   return 0;
  else
   return 1;
 }

 char* remove_Space(const char* remove)
 {
  const char* orgremove = remove;
  int operatorsize = 0;
  trim_size = 0;
  while (*remove != 0)
  {
   if (*remove != ' ')
   {
    trim_size++;
   }

   if (*remove == '+' || *remove == '/' || *remove == '*' || *remove == '-')
   {
    operatorsize++;
   }
   remove++;
  }
  char* trimchar = new char[trim_size + 1];

  while (*orgremove != 0)
  {
   if (*orgremove != ' ')
    *trimchar++ = *orgremove++;
   else
    orgremove++;

  }
  *trimchar = '\0';
  trimchar -= trim_size;
  int element = (operatorsize + operatorsize + 3);

  trim_size += element;
  return trimchar;
 }

 int compareOperation(char op)
 {
  if (op == '*' || op == '/')
   return 2;
  else if (op == '+' || op == '-')
   return 1;
  else if (op == '(')
   return 0;
  else
   return -1;
 }

 void change_Reverse_Poland(char* middle_formula)
 {
  char* middle_trimformula;
  middle_trimformula = remove_Space(middle_formula);
  if (!checkBrackets(middle_trimformula))
  {
   printf("괄호 갯수가 맞지 않습니다\n");
   delete[] middle_formula;
   return;
  }

  reverse_formula = new char[trim_size];
  char* origin_offset = reverse_formula;
  delete[] middle_formula;


  LinkedList_Stack mstack;

  bool first = true;
  while (*middle_trimformula != '\0' && trim_size > 0)
  {
   if (first)
   {
    if ((*middle_trimformula == '+' || *middle_trimformula == '-') && isdigit(*(middle_trimformula+1)))
    {
     *reverse_formula++ = *middle_trimformula++;
     *reverse_formula++ = *middle_trimformula++;
    }
    else if (isdigit(*middle_trimformula) || *middle_trimformula == '.')
    {
     *reverse_formula++ = *middle_trimformula++;
    }
    first = false;
   }
   else if (isdigit(*middle_trimformula) || *middle_trimformula == '.')
   {
    *reverse_formula++ = *middle_trimformula++;
   }
   else if (*middle_trimformula == '(')
   {
    mstack.push('(');
    middle_trimformula++;
   }
   else if (*middle_trimformula == ')')
   {
    while (mstack.cehckTop() != '(')
    {
     *reverse_formula++ = ' ';
     *reverse_formula++ = mstack.pop();
    }
    if (mstack.cehckTop() == '(')
     mstack.pop();
    middle_trimformula++;
   }
   else if (*middle_trimformula == '*' || *middle_trimformula == '/' || *middle_trimformula == '+' || *middle_trimformula == '-')
   {
    *reverse_formula++ = ' ';
    if (!mstack.isEmpty())
    {
     while ((compareOperation(mstack.cehckTop())) >= (compareOperation(*middle_trimformula)))
     {
      *reverse_formula++ = mstack.pop();
      *reverse_formula++ = ' ';
     }
     mstack.push(*middle_trimformula);
     middle_trimformula++;
    }
    else
    {

     mstack.push(*middle_trimformula);
     middle_trimformula++;
    }

   }
   else
   {
    delete[] origin_offset;
    printf("error wrong input");
    return;
   }

  }
  while (!mstack.isEmpty())
  {
   *reverse_formula++ = ' ';
   *reverse_formula++ = mstack.pop();
  }
  *reverse_formula++ = ' ';
  *reverse_formula = '\0';


  reverse_formula = origin_offset;
  int size = strlen(reverse_formula);

  printf("\n후위연산 표기수식 \n%s = ", reverse_formula);
  calc_Reverse_Ploand(reverse_formula);

 }

 void calc_Reverse_Ploand(char* p_reverse_formula)
 {
  char* deletepointer = p_reverse_formula;
  double op;
  LinkedList_Stack m_operand;

  //bool first = true;
  while (*p_reverse_formula)
  {
   //if (first)
   {
    if ((*p_reverse_formula == '+' || *p_reverse_formula == '-') && isdigit(*(p_reverse_formula + 1)))
    {
     m_operand.push(atof(p_reverse_formula));
     p_reverse_formula = getOp(p_reverse_formula);
    }
   }

   if (isdigit(*p_reverse_formula))
   {
    m_operand.push(atof(p_reverse_formula));
    p_reverse_formula = getOp(p_reverse_formula);
   }
   else if (*p_reverse_formula == '+')
   {
    m_operand.push(m_operand.pop() + m_operand.pop());
    p_reverse_formula = getOp(p_reverse_formula);
   }
   else if (*p_reverse_formula == '*')
   {
    m_operand.push(m_operand.pop() * m_operand.pop());
    p_reverse_formula = getOp(p_reverse_formula);
   }
   else if (*p_reverse_formula == '-')
   {
    op = m_operand.pop();
    m_operand.push(m_operand.pop() - op);
    p_reverse_formula = getOp(p_reverse_formula);

   }
   else if (*p_reverse_formula == '/')
   {

    op = m_operand.pop();
    if (op != 0)
     m_operand.push(m_operand.pop() / op);
    p_reverse_formula = getOp(p_reverse_formula);
   }
   else
   {
    printf("input error \n");
    delete[] deletepointer;
    return;
   }

  }

  printf(" %f\n", m_operand.pop());
  delete[] deletepointer;
 }

 char* getOp(char* op)
 {

  while (*op++ != ' ');

  return op;
 }
private:
 int trim_size;
 unsigned int size;

 char* reverse_formula;

};


void main()
{
 char* formula = new char[500];
 char c;
 int index;
 while (1)
 {
  index = 0;
  printf("\n수식을 입력하세요  종료: q \n");
  printf("사칙연산 (+,-,*,/) 및 () 괄호 계산 가능 단항연산자 -가능  종료: q \n");

  //while ((c = getchar()) != 10 && index < 500)
  //{
  // if (c >= 0 && c < 10)
  // {
  //  c += 48;
  // }
  // formula[index] = c;
  // index++;
  //}
  //formula[index] = 0;
  gets_s(formula,500);

  //  scanf_s("%s", formula, sizeof(char)*200);
  if (*formula == 'q') return;
  calculator cl(formula);
  cl.~calculator();

 }
 delete[] formula;
}