현재 위치

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

토큰 분리..

rainmon의 이미지
글쓴이: rainmon / 작성시간: 금, 2004/07/16 - 2:34오전

사용자가 문자열을 입력하는데.. 모양은 계산식 같은겁니다.
계산식엔 우선순위를 위해 괄호와 사칙연산, 그리고 한글변수명을 사용할 수 있습니다.
이런 조건으로 만들어진 문자열의 예를 들어보면

(변수1 + 변수2) * (변수1 / 변수2) + 변수3

한글로 된 변수명엔 이미 값이 있는 상태이구요.
저는 변수명에 해당하는 값으로 그 자리를 대치시켜주면 됩니다.
예를 들어 변수1 = 1, 변수2 = 2, 변수3 = 3 이란 값이 할당 되었다면
(1 + 2) * (1 / 2) + 3

이런형태로 바꿔줘야 하고 역으로도 표현가능해야 합니다.
참고로 사용자가 쓸 수 있는 한글변수명은 이미 정해져있는것이고
그 값도 이미 정해져 있습니다.

이문제를 해결하기 위해 Lex, Yacc 기타 다른 라이브러리를 사용할 수 없는 상황이고 정규표현식도 사용할 수 없습니다.
C++의 STL.. 이런것도 안됩니다.
어떻게하면 될런지 답변을 구합니다..

ps. 혹시나 해서 드리는 말인데.. 숙제나 과제물같은거 아닙니다.
이문제를 대신 풀어주시면 정말 고맙겠지만 그런걸 바라는것도 아니고요..
전 어떤 언어로 해야한다는 말도 안했듯이 그저 알고리즘만 구해보려는겁니다.
혼자선 버거운 상황이라.. 같이 고민해주시면 정말 고맙겠습니다.
[/list]

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

글쓴이: lsj0713 / 작성시간: 금, 2004/07/16 - 3:28오전

단순히 치환만을 원하는 거라면 평범한 문자열 검색 후 치환으로도 가능합니다. 검색은 무식하게 일대일로 비교해서 찾을 수도 있고, 알고리즘 책에 나오는 것들을 이용해도 됩니다. 치환은 검색해서 위치를 찾은 다음에 지운다음 덮어쓰면 되죠.

하지만 변수 기능이 지원되는 사칙연산 수식 계산기를 염두에 두고 계시다면... 본격적으로 파서를 만들어야 되겠죠.

(변수1 + 변수2) * (변수1 / 변수2) + 변수3

일단 위의 수식을 토큰(최소 단위. 영어 문장에서의 word라 생각하면 됩니다)으로 나누는 방법을 생각하십시오. 문법에 따라서는 strtok로 간단하게 해결할 수도 있고, 아니면 오토마타를 직접 구현하는 방법도 있습니다. 토큰으로 나눌 때 각 토큰이 어떤 타입인지(연산자인지, 숫자인지, 변수 이름인지)도 같이 구하면 나중에 일이 편해지겠죠.

기왕이면 계산기용 BNF 식을 한번 만들어보기를 권합니다.

( - 괄호
변수1 - 변수
+ - 연산자
변수2 - 변수
) - 괄호
* - 연산자
( - 괄호
변수1 - 변수
+ - 연산자
변수2 - 변수
) - 괄호

일단 위와 같이 토큰으로 나눈 다음에는 일이 쉬워집니다. 변수<->값 사이의 변환이라면 변수인 토큰들을 값으로 치환하면 되고, 결과값을 내는 거라면 중위식을 후위식으로 바꿔서 처리하는 방법도 있고 문법에 맞게 토큰을 트리로 구성해서 해결하는 방법도 있습니다. 재귀호출 함수로 무식하게 해도 되고요:-)

vinus의 이미지

글쓴이: vinus / 작성시간: 금, 2004/07/16 - 3:01오후

후위 연산식에 대해서 잘 생각 해보시면, 결과가 나올 듯 합니다.
쉽게 바이너리 트리를 이용하여구현 가능 하고, 스텍구조를 통해 연산이 가능 해 질 수 있습니다.

그러면 사칙 연산의 계산에 대한 것은 쉽게 해결 될 수 있지 않을까 생각 합니다.
그리고 다시 표현 할때 도 조금 더 생각 하면 되지 않을까 생각합니다.-- 물로 생략 가능한 괄호등이 생략되어 질수 있다면, 더욱 쉬워 지겠지요.

>>>행복한 웃음<<<

댓글 달기

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

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
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.