현재 위치

홈 ›› Forums ›› 공부 ›› 프로그래밍 QnA

띄어쓰기 없이 주어지는 infix를 postfix로 변환

canuyes의 이미지
글쓴이: canuyes / 작성시간: 월, 2013/04/29 - 5:56오후

안녕하세요.
현재 알고리즘 복습중인 학생입니다.
예전에 알고리즘을 짤 때는 아무 이상함을 못느끼고 그냥 넘어 갔었는데 오늘 다시보니 제가 큰걸 지나쳤던것 같습니다.
저는 띄어쓰기 없이 주어지는 중위표기식을 후위표기식으로 변환하는 것을 공부하고 있습니다.
변환 자체는 문제가 아니지만 주어진 중위표기식을 알맞은 토큰으로 자르는 것이 어렵네요...

저는 연산자가 나오면 연산자의 앞뒤로 공백을 삽입하여 나중에 strtok함수로 토크나이징 할 생각이었습니다.
input : 1+2+3 / output : 1 + 2 + 3
요렇게요.

그런데, 이방법으로 적용해보니 음수 인풋에 대해서는 적절한 대응을 할 수 없었습니다.
가령 input : 87*-12 / output : 87 * - 12
요렇게 되어 음수에 대한 정보가 소멸되어 버리고 맙니다.

결국 핵심은 수식에 사용되는 '-'가 단항연산자인지, 이항 연산자인지를 알아내는 것 인듯 싶습니다.
참고할만한 방법이나, 힌트를 주시면 감사하겠습니다.

Forums: 
프로그래밍 QnA
shint의 이미지

글쓴이: shint / 작성시간: 월, 2013/04/29 - 9:47오후

-를 _로 바꾸면 편합니다.
- (마이너스)를 _ (언더바)로 바꾸면. 쉽게 확인 가능합니다.

직접 구현하려니까. 생각보다 어렵네요... ㅇ_ㅇ;;
http://www.winapi.co.kr/clec/cpp2/19-3-2.htm 이거도 참고해보세요.

	strcpy(str, "1+2+3*34*_23+99");
	p = strtok(str, "+-*/");
	while(1)
	{
		if(p == NULL)
			break;
 
		printf("%s ", p);
		p = strtok(NULL, "+-*/");
	}
 
//출력 결과
//1 2 3 34 _23 99

----------------------------------------------------------------------------
젊음'은 모든것을 가능하게 만든다.

매일 1억명이 사용하는 프로그램을 함께 만들어보고 싶습니다.
정규 근로 시간을 지키는. 야근 없는 회사와 거래합니다.

각 분야별. 좋은 책'이나 사이트' 블로그' 링크 소개 받습니다. shintx@naver.com

익명 사용자의 이미지

글쓴이: 익명 사용자 / 작성시간: 화, 2013/04/30 - 12:11오전

연산자가 2회 연속으로 나타날때
두번째 연산자가 + 거나 - 라면
그것은 단항 연산자라고 판단한다...

...헛점이 있을까요?

gilgil의 이미지

글쓴이: gilgil / 작성시간: 화, 2013/04/30 - 8:29오전

strtok 함수를 사용하는 것은 한계가 있습니다.

1. regular expression을 이용하여 각각의 token을 추출한다.

2. BNF를 이용하여 제대로 구현한다.
http://en.wikipedia.org/wiki/Backus%E2%80%93Naur_Form

www.gilgil.net

댓글 달기

텍스트 포맷에 대한 자세한 정보

Filtered HTML

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

BBCode

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param>
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

Textile

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • You can use Textile markup to format text.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Markdown

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • Quick Tips:
    • Two or more spaces at a line's end = Line break
    • Double returns = Paragraph
    • *Single asterisks* or _single underscores_ = Emphasis
    • **Double** or __double__ = Strong
    • This is [a link](http://the.link.example.com "The optional title text")
    For complete details on the Markdown syntax, see the Markdown documentation and Markdown Extra documentation for tables, footnotes, and more.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Plain text

  • HTML 태그를 사용할 수 없습니다.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 줄과 단락은 자동으로 분리됩니다.
댓글 첨부 파일
이 댓글에 이미지나 파일을 업로드 합니다.
파일 크기는 8 MB보다 작아야 합니다.
허용할 파일 형식: txt pdf doc xls gif jpg jpeg mp3 png rar zip.
CAPTCHA
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.