[이산수학] Truth table
-
진리표 만들기
문제
괄호를 사용하지 않고, 연산자 우선순위는 ~가 가장 높고 나머지 연산자들의 우선순위는 모두 같다고
가정한다. 또한, 결합법칙은 왼쪽 결합법칙을 가지고 명제 변수들의 개수와 논리 연산자들의 개수를
받아서 합성 명제에 대한 진리표를 작성하는 프로그램을 작성하라.
(피연산자: 대문자, 연산자: 소문자, 진리표 출력은 피연산자의 사전 순으로, 진릿값은 내림차순 정렬)
생각해야 할 것
1) 명제를 받아서 피연산자 체크, 진리표와 연결 등을 해결
2) 명제를 연산하기 전에, 각 피연산자의 T, F값을 설정해줘야 함
3) 명제를 읽고 연산 및 출력
1) 피연산자 처리
합성 명제를 char 배열의 형태로 받아서 저장해두자.
피연산자를 사전순으로 나열해야 하므로 먼저 A~Z 중에서 사용된 피연산자를 따로 추출 해야한다.
map이나 배열 등 여러 방법이 있겠고 여기선 익숙한 배열을 사용하겠다.
명제에서 대문자는 피연산자, 소문자는 연산자라고 했으므로 대문자의 아스키코드는 65부터, 소문자는 97부터 시작이니 if 문을 사용해서 대문자일 때를 구분해서 피연산자를 처리하자.
단어의 수가 26개이니 int[26] 배열을 만들어 두고 피 산자에 -65를 해서 A~Z까지의 연산자 중 사용된 연산자를 표시하자.
char tmp;
std::cin >> tmp;
if (tmp < 91 && Trans[tmp - 65] == 0)
{
mVars.push_back(tmp);
mTrans[tmp - 65] = -1;
}
여기서 mTrans[] 배열이 피연산자를 표시해둔 배열이다.
배열 이름이 trans인 이유는 이후 사용한 진리표의 몇 번째에 저장되어있는지를 반환
하는 용도로 이 배열을 또 사용할 것이기 때문이다.
문제에서 사전 순으로 나열하라고 했으니 배열을 0부터 방문하며 값이 기본값(0)이
아니면 방문해서 값을 0부터 1씩 증가하는 값을 대입해두자.
ex) 피연산자가 P Q R이라면 0, 1, 2의 값을 대입
int order = 0;
for (int i = 0; i < 26; i++)
{
if(Trans[i] != 0)
mTrans[i] = order++;
}
(저 위에서 사용한 mVars를 사용해도 된다)
std::sort(mVars.begin(), mVars.end());
int order = 0;
for (int i = 0; i < mVarnum; i++)
mTrans[mVars[i] - 65] = order++;
이제 피연산자를 진리표와 연결했다고 볼 수 있다.
바로 연산에 들어가고 싶지만, 이 문제는 한 번만 연산하는 것이 아니라 피연산자들의
진릿값을 바꾸며 여러 번 계산해야 하므로 그 부분을 먼저 구현하자.
2) 피연산자의 진리표 작성
각 피연산자의 진리값을 저장해둘 배열을 만들어야 한다.
bool 배열을 new, delete를 이용해 동적 할당해도 되고 피연산자가 많아야 26개이니 bool[26]를 해두고 가진 피연산자의 수만큼만 사용해도 된다.
진릿값을 내림차순(1111->1110->1101…)으로 바꾸어가며 연산을 해야 한다.
이 부분을 필자는 재귀로 구현했다.
void PermutationRecur(int n) //n = 0으로 시작
{
if (n == 피연산자의 수)
{
3) 에서 작성할 계산함수();
진리표 출력 함수();(한 행)
return;
}
mTruth[n] = true;
PermutationRecur(n + 1);
mTruth[n] = false;
PermutationRecur(n + 1);
}
여기서 mTruth[]는 진릿값이 저장된 배열이다.
(피연산자가 A, D, E, F, G라면 A의 진릿값은 mTruth[0], D는mTruth[1]…)
재귀 순서는 내림차순으로 정렬하라고 하였으니 true를 우선으로, false는 뒤에 두었다.
변수가 5개라면 11111이 할당되고 계산+출력 후에 11110, 그다음은 11101 그다음은 11100… 순서로 진행될 것이다.
3) 합성명제 연산 및 출력
이제 맨 처음에 저장해둔 명제 배열을 읽으며 연산하면 된다.
피연산자용 stack과 연산자용 stack을 따로 사용할 것이고, 피연산자를 읽으면 아까 만들어둔 mTrans 배열에 -65 하고 집어넣어서 mTruth 배열의 순서를 꺼내고 그걸 다시 mTruth에 넣어서 각 피연산자에 맞는 진릿값(T, F)를 피연산자 스택에 넣을 것이다.
(효율을 높이고 싶다면 맨 처음으로 돌아가 합성명제의 피연산자들의 값을 미리
변환시키는 등 변화를 줘보자)
int i = 0;
while (i<int(mProp.size())) //합성 명제 읽기
{
//Operand
if (mProp[i] < 91)
{
mOperand.Push(mTruth[mTrans[mProp[i] - 65]]);
}
//operator
else
...
mOperand는 피연산자를 넣는 stack이다.
연산자 스택은 std::pair<char, int>를 이용해서 char에는 연산자를, int에는 그 연산자의 우선순위를 넣어줄 것이다. 우선순위는 ~가 1 나머지들은 모두 2를 주겠다. 연산자 스택이 비어있으면 무조건 넣어주고 시작한다.
스택의 top에 있는 연산자와 새로 읽은 연산자 중에 top이 우선순위가 높을 땐 top을 꺼내서 연산을 해주고, 그다음 top을 또 새로 읽은 연산자와 비교해주는 것을 계속 반복해주고(스택이 비거나 새 연산자가 이기면 멈춤) 반대의 경우는 읽은 연산자를 그대로 스택에 넣어주면 된다.
~을 연산할 경우는 피연산자 스택에서 하나만 꺼내서 연산한 후 그 값을 다시 넣고, 그 외의 연산자는 2개의 피연산자가 필요하니 두 개를 꺼내서 연산해주면 된다. 이를 반복하다가 명제를 끝까지 읽게 되면, 연산자 스택을 꺼내며 모두 연산해주면 된다.
- 만약 괄호가 있는 문제였다면 연산자 스택에 ‘(‘도 넣어주고 ‘)’를 읽는다면 연산자 스택에서 ‘(‘가 나올 때까지 연산을 진행해주는 식으로 구현하면 된다.
else //Operator
{
//비었으면 무조건 push
if (mOperator.Empty())
{
if (mProp[i] == 부정) //~
mOperator.Push({ mProp[i],1 });
else
mOperator.Push({ mProp[i],2 });
}
else
{
int nowpriority; //현재 읽은 연산자
if (mProp[i] == 부정)
nowpriority = 1;
else
nowpriority = 2;
//새 연산자가 이기거나 스택이 빌 때까지
while (mOperator.Top().second <= nowpriority)
{
연산하는 함수();
if (mOperator.Empty())
break;
}
//새 연산자를 push
if (mProp[i] == 부정)
mOperator.Push({ mProp[i],1 });
else
mOperator.Push({ mProp[i],2 });
}
}
i++;
}
//합성명제 다 읽음
while (!mOperator.Empty())
{
연산하는 함수();
}
}
연산함수는 연산자 스택에서 하나를 꺼내서 각 연산자에 맞는 계산을 해주면 된다.
부정이면 피연산자 스택에서 1개를 꺼내, !연산을, 논리곱은 &&, 논리합은 ||, 논리 함축은 A->B를 !A||B로 바꾸어 계산해주면 된다.
주의할 점은 피연산자 스택에서 먼저 나온 것이 B이고 그 뒤에 나온 것이 A라는 것.
이런 식으로 연산을 모두 끝내면 피연산자 스택에 최종 결괏값이 남아있을 것이다.
이후 mTruth[]의 값을 차례로 출력하고 마지막으로 스택의 값을 출력하면 진리표의 한 행이 완성, 이후 2) 에서 작성한 재귀함수대로 남은 행들을 전부 계산, 출력해줄 것이다.