C# - 중위식을 후위식으로 변환하는 예제
이번엔 별다르게 쓸 이야기는 없고, 단순히 다음의 글에 실린 파이썬 코드를 C#에 대응시켜 변환해 봤습니다.
후위식 변환
; http://soooprmx.com/wp/archives/5127
첨부 파일에도 넣어두었지만, 다음은 해당 코드입니다.
using System;
namespace ConsoleApplication1
{
class Program
{
static void Main(string[] args)
{
Console.WriteLine(Expression.ConvertToPostFix("A + B * C"));
// 출력: A B C * +
Console.WriteLine(Expression.ConvertToPostFix("( A + B ) * C"));
// 출력: A B + C *
Console.WriteLine(Expression.ConvertToPostFix("( A + B ) * ( C + D )"));
// 출력: A B + C D + *
}
}
class Expression
{
public static string ConvertToPostFix(string expStr)
{
// 1. 수식을 각 토큰별로 구분하여 읽어들인다
string[] tokens = expStr.Split(' ');
string[] ops = new string[] { "+", "-", "*", "/", "(", ")" };
Dictionary<string, int> precs = new Dictionary<string, int>
{
["*"] = 2,
["/"] = 2,
["+"] = 1,
["-"] = 1,
["("] = 0,
};
Stack<string> opStack = new Stack<string>(); // 스택
List<string> output = new List<string>(); // 출력 리스트
foreach (string item in tokens)
{
if (ops.Contains(item) == false)
{
// 2. 토큰이 피 연산자이면 출력 리스트에 넣는다.
output.Add(item);
}
else if (item == "(")
{
// 3. 토큰이 왼쪽 괄호이면 스택에 푸시한다.
opStack.Push(item);
}
else if (item == ")")
{
// 5. 토큰이 오른쪽 괄호이면 왼쪽 괄호가 나올 때까지 스택에서 팝하여 순서대로 리스트에 넣는다.
while (opStack.Peek() != "(")
{
output.Add(opStack.Pop());
}
// 왼쪽 괄호 자체는 버린다.
opStack.Pop();
}
else
{
// 4. 토큰이 연산자이면,
while (opStack.Count != 0)
{
if (precs[opStack.Peek()] >= precs[item])
{
// 스택에 있는 연산자의 우선 순위가 자신보다 높거나 같다면 출력 리스트에 이어 붙여준다.
output.Add(opStack.Pop());
}
else
{
break;
}
}
opStack.Push(item);
}
}
// 6. 더 이상 읽을 토큰이 없다면, 스택에서 연산자를 팝하여 붙인다.
while (opStack.Count != 0)
{
output.Add(opStack.Pop());
}
return string.Join(" ", output);
}
}
}
C# 소스코드가 파이썬에 비해 코드량이 많을지언정, Visual Studio의 디버깅 기능을 켜놓고 Step-into/over 및 Watch 창을 이용해 따라가시면 훨씬 빠르게 코드를 이해할 수 있답니다. ^^
[이 글에 대해서 여러분들과 의견을 공유하고 싶습니다. 틀리거나 미흡한 부분 또는 의문 사항이 있으시면 언제든 댓글 남겨주십시오.]