[중위표기법 -> 후위표기법 예제]
/*
Write the poostfix form of the following expressions:
다음 식들을 후위표기법으로 표기하라
*/
a) A*B*C -> ABC**
b) -A+B-C+D -> -AB+-CD+
c) A*-B+C -> A-B*C+
d) (A+B)*D+E/(F+A*D)+C -> AB+D*EFAD*+/+C+
e) A&&B||C||!(E>F) -> AB&&C||EF>!||
f) !(A&&!((B<C)||(C>D)))||(C<E) -> ABC<CD>||!&&!CE<||
[코드 예제]
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
typedef char Token;
//기존에 정의한 스택
template <typename T>
class Stack
{
private:
T *stack; //스택배열
int top; //제일 마지막에 삽입된 원소
int capacity; //배열 크기
public:
Stack(int stackCapacity = 10) :capacity(stackCapacity)
{
if (capacity < 1)
throw "Stack capacity must be >0";
stack = new T[capacity];
top = -1;
}
~Stack()
{
delete[]stack;
}
bool IsEmpty() const
{
return top == -1;
}
T &Top() const
{
if (IsEmpty())
throw "Stack is empty";
return stack[top];
}
void Push(const T &x)
{
if (top == capacity - 1)
{
ChangeSize1D(stack, capacity, 2 * capacity);
capacity *= 2;
}
stack[++top] = x;
}
void Pop()
{
if (IsEmpty())
throw "Stack is empty. Can't Delete";
stack[top--].~T(); //destructor for T(처음보는 활용법)
}
template <typename T> //이걸 추가하지 않으면 basic operator<< 라고 여겨져 오류가 납니다
friend ostream &operator<<(ostream &os, Stack<T> &s); //출력
};
template <typename T>
ostream &operator<<(ostream &os, Stack<T> &s)
{
os << "현재 Top: " << s.Top() << endl;
for (int i = 0; i <= s.top; i++)
os << i + 1 << ": " << s.stack[i] << endl;
return os;
}
template <typename T>
void ChangeSize1D(T *&a, const int oldSize, const int newSize)
{
if (newSize < 0)
throw "New length must be >=0";
T *temp = new T[newSize];
int number = min(oldSize, newSize);
copy(a, a + number, temp);
delete[]a;
a = temp;
}
class Expression
{
public:
string expression;
int idx;
Expression(const string str) :expression(str)
{
idx = 0;
}
};
Token NextToken(Expression &exp)
{
Token token;
token = exp.expression[exp.idx++];
return token;
}
bool IsOperand(char x) //숫자인가
{
if (x == '+' || x == '-' || x == '*' || x == '/' || x == '%' || x == '#' || x == '(' || x == ')')
return false;
return true;
}
int isp(char x) //in stack precedence(스택 안에 있는) 우선순위
{
int priority;
switch (x)
{
case '#':
priority = 8;
break;
case '*':
priority = 2;
break;
case '/':
priority = 2;
break;
case '%':
priority = 2;
break;
case '+':
priority = 3;
break;
case '-':
priority = 3;
break;
default:
priority = 8;
}
return priority;
}
int icp(char x) //incoming precedence(다음에 스택에 들어올) 우선순위
{
int priority;
switch (x)
{
case '*':
priority = 2;
break;
case '/':
priority = 2;
break;
case '%':
priority = 2;
break;
case '+':
priority = 3;
break;;
case '-':
priority = 3;
break;
default:
priority = 0;;
}
return priority;
}
void Postfix(Expression exp)
{
Stack<Token> stack;
stack.Push('#');
for (Token x = NextToken(exp); x != '#'; x = NextToken(exp))
{
if (IsOperand(x))
cout << x;
else if (x == ')')
{
while (stack.Top() != '(')
{
cout << stack.Top();
stack.Pop();
}
stack.Pop();
}
else
{
while (isp(stack.Top()) <= icp(x))
{
cout << stack.Top();
stack.Pop();
}
stack.Push(x);
}
}
while (!stack.IsEmpty())
{
if(stack.Top()!='#') //#은 생략
cout << stack.Top();
stack.Pop();
}
cout << endl;
}
void Eval(Expression e) //현재로써는 소수점이 나오면 반올림을 한다
{
Stack<Token> stack;
for (Token x = NextToken(e); x != '#'; x = NextToken(e))
{
if (IsOperand(x))
{
stack.Push(x-48); //아스키코드이므로 -48
//cout << x << endl;
}
else
{
Token val1 = stack.Top();
//cout << "val1: " << (int)val1 << endl;
stack.Pop();
Token val2 = stack.Top();
//cout << "val2: " << (int)val2 << endl;
stack.Pop();
//cout << "x: " << x << endl;
if (x == '+')
stack.Push(val1+val2);
else if (x == '-')
stack.Push(val1 - val2);
else if (x == '*')
stack.Push(val1*val2);
else if (x == '/')
stack.Push(val1 / val2);
else if (x == '%')
stack.Push(val1%val2);
}
}
cout << "결과: " << (int)stack.Top() << endl;
}
int main(void)
{
string str("(1+2)*4+5/(6+1*4)+3#");
Expression exp(str);
Postfix(exp);
string str2("12+4*5514*+/+3+#");
Expression exp2(str2);
Eval(exp2);
cout << "원래 값: 15.5" << endl << "소숫점 계산을 하려면 좀 더 보완해야합니다" << endl;
return 0;
}
[참고] Fundamentals of Data Structures in C++(Horowitz, Sahni, Mehta) 원서
*영어로 적혀있는 문제를 제가 의역한 것이기 때문에 오역이 있을 수 있습니다. 양해 부탁드립니다.
*아직 많이 부족한 코드이므로 나중에 시간이 날 때 다시 보완하도록 하겠습니다!
'C++ > Fundamentals of Data Structures in C++(Horowitz)' 카테고리의 다른 글
| C++ Fundamentals of Data Structures(C++ 자료구조론) 4.3 연습문제 (0) | 2017.08.19 |
|---|---|
| C++ Fundamentals of Data Structures(C++ 자료구조론) 4.2 연습문제 (0) | 2017.08.16 |
| C++ Fundamentals of Data Structures(C++ 자료구조론) 3.5 미로 예제 (4) | 2017.08.13 |
| C++ Fundamentals of Data Structures(C++ 자료구조론) 3.4 연습문제 (2) | 2017.08.13 |
| C++ Fundamentals of Data Structures(C++ 자료구조론) 3.3 연습문제 (0) | 2017.08.11 |