LISP은 괄호로 유명한 언어다. 이 문제는 LISP 형태로 표현된 4칙연산 산술식을 계산하는 계산기 프로그램을 작성하는 것이다.
LISP 표현식은 여는 괄호와 공백으로 구분된 항(term)의 목록 그리고 닫는 괄호로 만들어진다. 첫 번째 항은 +, -, *, /와 같은 심볼이며 나머지 항은 1, 2, 10, -10 등의 정수 혹은 또다른 LISP 표현식이 될 수 있다. 말하자면 연산자들이 가변 길이 인자를 받는 셈이다.
더하기의 경우 (+ 1 2 3)은 6이다. (+)만 단독으로 사용된 경우는 0이다. 곱하기의 경우는 기본 값이 1이고, 빼기와 나누기는 인자가 최소 하나 이상 있어야 한다. 아래는 빼기와 곱하기의 예를 보여준다. (화살표는 결과값을 나타낸다)
(- 10 3) → 7
(- 10 3 5) → 2
(* 2 3) → 6
(* 2 3 4) → 24
(+) → 0
-5 → -5
괄호가 중쳡된 경우는 아래와 같다.
(* (+ 2 3) (- 5 3)) → 10
(/ (+ 9 1) (+ 2 3)) → 2
모두 괄호로 묶여있기 때문에 +, -, *, / 연산자 사이의 우선순위는 따로 신경쓸 필요 없다.
23개의 풀이가 있습니다.
아래의 함수를 만들면 될 것 같다.
int eval(const char* s);
그런데 리스트를 파싱하는 함수가 (+ 1 (- 1 2) 3)를 처리한다면, 중첩된 (- 1 2)에 대해서 재귀적으로 호출할 수 있어야 할 것 같다. 이때, 문자열 전체를 처리하지 않을 것이고 닫힌 괄호까지만 처리하면 된다. 그러면 원래의 리스트를 처리하는 함수는 파싱하고 남은 부분 3)을 재귀호출 함수에서 받아올 수 있어야 한다. 즉, 입력 커서 역할을 하는 const char* s만 전달해서는 소용없고 함수 호출하여 이 값을 업데이트 해야 한다. 이중포인터로 전달하는 것도 방법이겠지만 context라고 감싸서 전달하는 것이 낫다.
typedef struct context context_t;
struct context {
const char * s;
};
int eval(context_t* c);
그러면 main()은 다음처럼 만들어볼 수 있다. (free는 생략)
context_t* context(const char* s) {
context_t* c = (context_t*)malloc(sizeof(context_t));
c->s = s;
return c;
}
int main(int argc, const char * argv[]) {
printf("%d\n", eval(context("1")));
printf("%d\n", eval(context("123")));
printf("%d\n", eval(context("(+)")));
printf("%d\n", eval(context("(+ 2 3)")));
printf("%d\n", eval(context("(+ 1 2)")));
printf("%d\n", eval(context("(* 1 2 (- 1 2 -3))")));
return 0;
}
간단한 양의 정수만 고려해보자.
int eval(context_t* c) {
return num(c);
}
int num(context_t* c) {
int n = 0;
while (isdigit(*c->s)) {
n *= 10;
n += *c->s - '0';
c->s++;
}
return n;
}
음의 정수까지 고려한다면..
int eval(context_t* c) {
if (isdigit(*c->s))
return num(c);
if (*c->s == '-') {
++c->s;
return -num(c);
}
return 0;
}
드디어 리스트를 처리해보자
int eval(context_t* c) {
if (isdigit(*c->s))
return num(c);
if (*c->s == '-') {
++c->s; // skip -
return -num(c);
}
assert(*c->s == '(');
++c->s; // skip (
return list(c);
}
list() 는 첫 항이 +,-,*,/ 여야 한다. 나머지는 공백을 건너뛰고 닫힌 괄호까지 처리한다.
그런데 -는 첫 항에서 나머지를 빼고, / 는 첫 항에서 나머지를 나눠나간다.
void spaces(context_t* c) {
while (*c->s == ' ')
c->s++;
}
int list(context_t* c) {
char op = *c->s++;
int value;
if (op == '-' || op == '/') { // should have 1+ args
spaces(c);
value = eval(c);
} else if (op == '+') {
value = 0;
} else {
value = 1;
}
while (*c->s != ')') {
spaces(c);
value = calc(op, value, eval(c));
}
++c->s; // skip )
return value;
}
첫번째 방법: 정규식 이용
import re
run = lambda e, *_tuple: str(eval(e.join(_tuple)))
ins = lambda _string, start, end: _string[:start] + '"' + _string[start:end] + '"' + _string[end:]
while __name__ == '__main__':
s = input('>>>')
for i in reversed([*re.finditer(r'([^() ]+)', s)]):
s = ins(s, *i.span())
for i in [('(', 'run('), ' ,']:
exec('s = s.replace("%s", "%s")'%(*i,))
print(eval(s))
두번째 방법: 정규식 없음
def lisp_eval(args):
return eval(args[0].join(args[1:]))
def divide_eval(_list):
res = []
k = 0
for n, i in enumerate(_list):
if i == '(':
k += 1
if i == ')':
k -= 1
if i == ' ' and k == 0:
res.append(n)
return res
def divide(_list):
res = []
s = _list[:]
target = reversed(sorted(divide_eval(_list)))
for i in target:
res.append(s[i+1:])
s = s[:i]
res.append(_list[0])
res.reverse()
return res
def interpret(s):
if len(s) == 3:
return 0
s = s[1:-1]
s_list = divide(s)
for i in range(1, len(s_list)):
if '(' in s_list[i]:
s_list[i] = str(interpret(s_list[i]))
return lisp_eval(s_list)
while __name__ == '__main__':
print(interpret(input('>>>')))
파이썬 3.5.2 64
Ruby
eval 사용(풀이1), 스택 구현(풀이2). 두가지로 풀이. (수정 : 풀이 2 추가)
풀이 1. s-expression을 람다 약기로 변환한 뒤 eval.
calc = proc {|op,*args| args.reduce(op) || 0 }
lisp_eval = ->exp { eval exp.gsub(/[(\s)]/, '('=>"calc[:", ' '=>',', ')'=>']') }
풀이 2. 토큰을 차례차례 스택에 push. 토큰이 ")"면 스택에서 직전의 연산자까지 꺼내서 계산. 이를 반복.
calc = proc {|op,*args| args.reduce(op) || 0 }
eval_top = ->s { t=[]; t.unshift(s.pop) until t[0].is_a? Symbol; s << calc[*t] }
lisp_eval = ->str do
tokens = str.gsub(/[()]/, "("=>"",")"=>" )").split.
map {|e| e == ")" ? e : e =~ /[[:digit:]]/ ? e.to_i : e.to_sym }
tokens.reduce([]) {|stack,e| e == ")" ? eval_top[stack] : stack << e }.pop
end
Test
# tests : arity 1, 3, 4, nested s-exp, complex s-exp
cases = ["(+)"] +
["(- 10 3)", "(* 2 3)"] +
["(- 10 3 5)", "(* 2 3 4)"] +
["(* (+ 2 3) (- 5 3))", "(/ (+ 9 1) (+ 2 3))"] +
["(* 1 (- 2 3) 4 (+ 2 -1) 3)" ]
expect( cases.map(&lisp_eval) ).to eq [0, 7, 6, 2, 24, 10, 2, -12]
Output
lisp_eval["(+ 2 3 5 (* 2 5) (* -2 5))"] #=> 10
댓글을 본 뒤 수정했습니다. p.s. 그러고보니 그냥 스택을 쓸껄 그랬군요..
#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;
#define PLUS 0
#define MINU 1
#define MULT 2
#define DIVD 3
int pos;
float Lisp(string input)
{
float result = 0;
int mark = -1;
float nFirstNum = 0.0; //앞 숫자
float nSecondNum = 0.0; //뒷 숫자
float returnResult = 0.0;
bool bFristInput = false;
bool bSecondInput = false;
//printf("input: %s\n", input.c_str());
while(1)
{
//입력받은 수식의 끝 체크
if(pos >= input.length())
{
break;
}
//닫는 괄호 연산 끝 리턴
if(input[pos] == ')')
break;
//여는 괄호가 나오면 다시 함수 호출
if(input[pos] == '(')
{
pos++;
returnResult = Lisp(input);
if(!bFristInput)
{
nFirstNum = returnResult;
bFristInput = true;
}
else
{
nSecondNum = returnResult;
bSecondInput = true;
}
}
#pragma region 부호결정
//부호 결정
if(mark == -1)//부호가 아직 결정이 안됐다면
{
if(input[pos] == '+')
mark = PLUS;
else if(input[pos] == '-' )
mark = MINU;
else if(input[pos] == '*' )
mark = MULT;
else if(input[pos] == '/' )
mark = DIVD;
}
#pragma endregion
#pragma region 문자열을 숫자로
//숫자 범위면
if(input[pos] >= '0' && input[pos] <= '9')
{
int i = 0;
//첫 번째 숫자가 비어있으면
if(!bFristInput)
{
for(i = pos; input[i] >= '0' && input[i] <= '9'; i++)
{
nFirstNum *= 10; // 자리수 증가
nFirstNum += input[i] - '0';
}
bFristInput = true;
}
//두 번째 숫자를 구한다.
else
{
for(i = pos; input[i] >= '0' && input[i] <= '9'; i++)
{
nSecondNum *= 10; // 자리수 증가
nSecondNum += input[i] - '0';
}
bSecondInput = true;
}
pos = i - 1;
}
#pragma endregion
#pragma region 연산
//연산
if(bSecondInput)
{
switch(mark)
{
case PLUS:
//printf("%d + %d\n", nFirstNum, nSecondNum);
nFirstNum += nSecondNum;
break;
case MINU:
//printf("%d - %d\n", nFirstNum, nSecondNum);
nFirstNum -= nSecondNum;
break;
case MULT:
//printf("%d * %d\n", nFirstNum, nSecondNum);
nFirstNum *= nSecondNum;
break;
case DIVD:
if(nSecondNum == 0)
return -999;
nFirstNum /= nSecondNum;
break;
}
nSecondNum = 0;
bSecondInput = false;
}
#pragma endregion
pos++;
result = nFirstNum;
}
//printf("return: %d\n", result);
return result;
}
int main (int argc, char *argv[])
{
string input[7];
input[0]= "(* (+ 2 3) (- 5 3))";
input[1] ="(/ (+ 9 1) (+ 2 3))";
input[2] = "(* (- 10 3 5) (+ 2 5) (/ 10 2))";
input[3] = "(/ (* 12 12 12 12) (* 2 6) (/ 10 5))";
input[4] = "(+ (+ (- 3 5) (* 1 3)) (+ 2 5))";
input[5] = "(* (/ (+ (- 3 5) (+ 4 1)) (+ 1 1)) (- 1 2)) ";
input[6] = "(+ (* 2 2 2 2) (/ 64 2 2 2))";
int i = 0;
for(i = 0; i < 7; i ++)
{
pos = 0;
printf("result: %.3f\n", Lisp(input[i]));
}
return 0;
}
아, LISP의 사칙 연산은 단순한 이항연산이 아니었네요;; 죄송합니다. 문제를 뜨문뜨문 보는 바람에 잘못 풀었네요...
검색해보니 LIST의 연산자는 뒤에 몇 개의 피연산자가 오는지에 따라서 다르게 작동하네요.
(+ 1) : 단항연산자로 동작(+ 1 2) : 이항연산자로 동작(+ 1 2 3...) : 피연산자를 리스트로 보고 이를 fold함. Swift3으로 다시 작성해봤습니다. 이곳에서 확인할 수 있습니다.
풀이한 과정은 이렇습니다.
이를 파싱하면 (연산자, [피연산자의 리스트]) 형식의 데이터를 얻게 됩니다.
기본적으로 피연산자가 정수라 가정하고 커서를 옮겨가면서 정수값으로 파싱합니다. 그러다 중간에 여는 괄호를 다시 만나면 재귀호출을 통해서 중첩된 수식 부분을 파싱합니다. 파싱된 결과는 재귀 enum 타입으로 처리했고, 평가는 이 타입의 메소드로 구현했습니다.
enum Expression {
case op(Character)
case number(Int)
indirect case operand(Expression, [Expression])
func evaluate() -> Int? {
func operation(_ x: Character) -> ((Int?, Int) -> Int?)? {
let op: (Int, Int) -> Int?
switch x {
case "*": op = { $0 * $1 }
case "/": op = { x, y in return y != 0 ? x / y : nil }
case "+": op = { $0 + $1 }
case "-": op = { $0 - $1 }
default: return nil
}
return { x, y in
guard let x = x else { return nil }
return op(x, y)
}
}
switch self {
case let .number(i): return i
case let .operand(.op(x), values):
guard values.count > 0 else { return 0 }
guard let ops = operation(x) else { return nil }
let vs = values.flatMap{ $0.evaluate() }
return vs.dropFirst().reduce(vs[0], ops)
default: return nil
}
}
}
func parse(expr: String, at index: String.Index? = nil) -> (Expression?, String.Index) {
var cursor = index ?? expr.startIndex
var operands: [Expression] = []
guard expr[cursor] == "(" else { return (nil, cursor) }
cursor = expr.index(after:cursor)
let op: Expression = Expression.op(expr[cursor])
var nodeStart = expr.index(after:cursor)
while expr[cursor] != ")" && cursor < expr.endIndex {
if expr[cursor] == " " {
if let i = Int(expr[nodeStart..<cursor]) {
operands.append(.number(i))
}
nodeStart = expr.index(after:cursor)
}
else if expr[cursor] == "(" {
let (subexpr, nextposition) = parse(expr:expr, at:cursor)
if let subexpr = subexpr { operands.append(subexpr) }
nodeStart = nextposition
cursor = expr.index(after:nodeStart)
continue
}
cursor = expr.index(after: cursor)
}
if nodeStart < cursor, let i = Int(expr[nodeStart..<cursor]) {
operands.append(.number(i))
}
return (Expression.operand(op, operands), cursor)
}
let s = "(+ 10 9 8 (* 5 4) 7 (/ 8 2) 6)"
if case let (s?, _) = parse(expr:s), let result = s.evaluate() {
print(result)
} else {
print("invalid expression")
}
일단 입력에는 오류가 없다고 가정하고 시작합니다.
LISP 표현식은 전위식 표기와 동치이기 때문에 사실상 괄호는 무시해도 됩니다.
따라서 괄호를 제외한 문자들을 공백으로 나누고
연산자와 피연산자를 구분, (피연산자는 정수만) 연산자는 문자 그대로, 피연산자는 정수로 변환해준 후
이를 뒤집어서 스택으로 만듭니다. (사실 .pop(0) 해도 되기 때문에 뒤집지 않아도 됩니다.)
평가방식은 다음과 같습니다.
def do(s=None):
ops = {
'*': lambda x, y: x * y,
'/': lambda x, y: x / y,
'+': lambda x, y: x + y,
'-': lambda x, y: x - y,
}
def getInput():
nonlocal s
if s is not None:
inp = s
else:
inp = input()
inp = ''.join(x for x in inp if x not in '()').split()
temp = []
for token in inp:
if token.isdigit() or (token[0] == '-' and token[1:].isdigit()):
temp.append(int(token))
elif token in '+-/*':
temp.append(token)
return temp[::-1]
def evaluate(st):
x = st.pop()
if isinstance(x, int):
return x, st
if x in ops:
a, st = evaluate(st)
b, st = evaluate(st)
return ops[x](a, b), st
return evaluate(getInput())[0]
print(do('(- 10 3)'))
import re
def eval(op, variables):
variable = list(map(int, variables.split()))
if op == '+':
out = sum(variable)
elif op == '-':
out = variable[0]
for i in range(2,len(variable)):
out -= variable[i]
elif op == '*':
out = 1
for i in range(len(variable)):
out *= variable[i]
elif op == '/':
out = variable[0]
for i in range(2,len(variable)):
out /= variable[i]
return out
def f(input_string):
p = re.compile('\(([\+\-\*\/])\s(:?[^\(^\).]+)\)')
m = p.search(input_string)
out = eval(m.group(1),m.group(2))
output_string = input_string.replace(m.group(), str(out))
try:
f(output_string)
except:
print(output_string)
pass
input_string = '(* (- 32 3) (- 32 4 8))'
f(input_string)
C(99)
gcc -std=c99 -pedantic-errors -W -Wall
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <stdbool.h>
#include <assert.h>
// TokenStream 구조체
typedef enum _type { OPERATOR, NUMBER } Type; // 연산자와 숫자 타입
typedef struct _token
{
Type type;
int content;
} Token;
typedef struct _tokenStrem
{
Token tokenArray[100];
int cursor; // 토큰스트림의 현재 가리키고 있는 인덱스
int size; // 토큰스트림 사이즈
} TokenStream;
// Stack 구조체
typedef struct _stack
{
Token arr[100]; // 토큰으로 이뤄진 배열스택
int cur; // 현재 가리키고 있는 인덱스
} Stack;
static TokenStream ts; // TokenStream은 접근하기 쉽게 전역변수로 선언
// TokenStream Operator
Token GetToken(void);
void InitTokenStream(const char * expr);
void ShowToken(Token t);
void ShowTokenStream(void); // 디버깅용
// Stack Operator
Stack * StackInit(void);
void StackPush(Stack * pstack, Token t);
Token StackPop(Stack * pstack);
bool StackIsEmpty(Stack * pstack);
Token Calc(void)
{
Token tmp, left, right, op;
Stack * peek = StackInit(); // 일단 담는다
Stack * calc = StackInit(); // ')'을 만나면 '('까지 따로 담아 계산한다
while (ts.cursor < ts.size)
{
tmp = GetToken();
while (tmp.content != ')')
{
StackPush(peek, tmp);
tmp = GetToken();
}
// tmp.content == ')'...')' 버려짐
while (tmp.content != '(')
{
tmp = StackPop(peek);
StackPush(calc, tmp); // 계산하기위한 스택에 넣는다
}
// tmp.content == '('
StackPop(calc); // '(' 버림
op = StackPop(calc); // 한항의 연산자
left = StackPop(calc); // 첫번째 숫자
while (! StackIsEmpty(calc))
{
right = StackPop(calc);
switch (op.content)
{
case '+': left.content = left.content + right.content; break;
case '-': left.content = left.content - right.content; break;
case '*': left.content = left.content * right.content; break;
case '/': left.content = left.content / right.content; break;
default: assert(0);
}
}
// calc 스택이 비었음
StackPush(peek, left); // 한항을 계산한 결과는 peek 스택에 다시 푸시
}
// TokenStream이 끝남
return left;
}
int main(void)
{
const char * expr1 = "(* (+ 1 1 3) (- 3 1) (+ 1 4) )";
printf("%s = ", expr1);
InitTokenStream(expr1);
ShowToken(Calc());
const char * expr2 = "(/ (+ 9 1) (+ 2 3))";
printf("%s = ", expr2);
InitTokenStream(expr2);
ShowToken(Calc());
const char * expr3 = "(- 10 3 5)";
printf("%s = ", expr3);
InitTokenStream(expr3);
ShowToken(Calc());
const char * expr4 = "(* (+ 2 3) (- 5 3))";
printf("%s = ", expr4);
InitTokenStream(expr4);
ShowToken(Calc());
return 0;
}
// 토큰스트림에서 토큰 하나를 받음
Token GetToken(void) { return ts.tokenArray[ts.cursor++]; }
// 문자열을 TokenStream으로 변환
void InitTokenStream(const char * expr)
{
Token tmpToken;
int tmpNum;
int i = 0;
while (*expr)
{
if (isdigit(*expr))
{
sscanf(expr, "%d", &tmpNum);
tmpToken.type = NUMBER;
tmpToken.content = tmpNum;
ts.tokenArray[i++] = tmpToken;
while (isdigit(*expr))
expr++;
}
else if (isspace(*expr))
{
expr++;
}
else
{
tmpToken.type = OPERATOR;
tmpToken.content = *expr;
ts.tokenArray[i++] = tmpToken;
expr++;
}
}
ts.size = i;
ts.cursor = 0;
}
// Token 하나를 타입에 맞게 출력한다
void ShowToken(Token t)
{
if (t.type == OPERATOR)
printf("%c \n", t.content);
else
printf("%d \n", t.content);
}
// 토큰스트림이 잘 됐는지 확인하는 디버깅용
void ShowTokenStream(void)
{
int i;
for (i = 0; i < ts.size; i++)
{
if (ts.tokenArray[i].type == OPERATOR)
printf("[OPERATOR] %c \n", ts.tokenArray[i].content);
else
printf("[NUMBER] %d \n", ts.tokenArray[i].content);
}
printf("TokenStream size = %d \n", ts.size);
putchar('\n');
}
// 스택 초기화
Stack * StackInit(void)
{
Stack * ret = malloc(sizeof (Stack));
ret->cur = -1;
return ret;
}
void StackPush(Stack * pstack, Token t)
{
pstack->arr[++pstack->cur] = t;
}
Token StackPop(Stack * pstack) { return pstack->arr[pstack->cur--]; }
bool StackIsEmpty(Stack * pstack) { return pstack->cur == -1; }
/*
문자열을 토큰으로 쪼개어 토큰스트림을 만듭니다.
토큰스트림에서 토큰 하나씩을 받아 peek 스택에 담습니다.
')' 토큰을 만나면 peek 스택에 담아둔 토큰중 '('를 만날때까지 calc 스택으로 push하고,
peek 스택에서는 pop을 합니다.
calc 스택에서는 스택이 빌때까지 계산을 한뒤 peek스택으로 push합니다.
스택을 두개 사용하여 한곳에서는 임시로 토큰을 받고, ( )사이의 숫자와 연산자는 calc스택에 다시
담아 연산을 한뒤 다시 되돌려주는 방법으로 했습니다.
*/
def func(s):
nums,X = list(), 0
for y in range(len(s)):
if s[y].isnumeric() and y > X:
tmp,c = s[y],1
while s[y+c].isnumeric():
tmp += s[y+c]
c += 1
X = y+c
nums.append(tmp)
return str(eval(s[1].join(nums)))
l,r = -1,-1
s_list = ['(- 10 3)','(- 10 3 5)','(* 2 3)',\
'(* 2 3 4)','(* (+ 2 3) (- 5 3))','(/ (+ 9 1) (+ 2 3))']
for string in s_list:
while '(' in string:
for x in range(len(string)):
if string[x] == '(':
l = x
elif string[x] == ')':
r = x
string = string[:l]+func(string[l:r+1])+string[r+1:]
break
print(string)
#### 2017.02.04 D-383 ####
이제 막 String 클래스를 배우는 초보라서 아는 방법으로 열심히 해봤습니다ㅠㅠ 문제점도 많지만....
package coading.lisp;
import java.util.*;
public class Lisp_v2 {
public static void main(String[] args) {
System.out.print("Lisp 연산식을 입력하세요 : ");
Scanner robot = new Scanner(System.in);
String input = robot.nextLine();
while (true) {
String tmp = input.substring(input.lastIndexOf("(", input.indexOf(")")) + 1, input.indexOf(")")) + " ";
String tmp_num_s = "";
List<Integer> tmp_num = new ArrayList<Integer>();
char symbol = 0;
for (int i = 0; i < tmp.length(); i++) {
if ((tmp.charAt(i) == '+' || tmp.charAt(i) == '-' || tmp.charAt(i) == '*' || tmp.charAt(i) == '/')
&& i == 0) {
symbol = tmp.charAt(i);
} else if (tmp.charAt(i) != ' ') {
if (tmp.charAt(i) != ')') {
tmp_num_s += tmp.charAt(i);
}
} else {
if (tmp_num_s != "") {
tmp_num.add(Integer.decode(tmp_num_s));
tmp_num_s = "";
}
}
}
int temp = tmp_num.get(0);
for (int i = 1; i < tmp_num.size(); i++) {
switch (symbol) {
case '+':
temp += tmp_num.get(i);
break;
case '-':
temp -= tmp_num.get(i);
break;
case '*':
if (tmp_num.get(i) != 0)
temp *= tmp_num.get(i);
else
temp *= 1;
break;
case '/':
if (tmp_num.get(i) != 0)
temp /= tmp_num.get(i);
else
temp /= 1;
break;
}
}
System.out.println(input.replace("(" + tmp.trim() + ")", String.valueOf(temp)));
input = input.replace("(" + tmp.trim() + ")", String.valueOf(temp));
if (input.indexOf('(') == -1) {
break;
}
}
}
}
import java.util.ArrayList;
import java.util.List;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
public class LISPCalculator {
static Node root = null;
static Node current = null;
static Node key = null;
public static void main(String[] args) {
final String ss = "(* (+ 2 3) (- 5 3))";
final Pattern p = Pattern.compile("\\*|\\+|/|-(?!\\d)|-?\\d{1,30}|\\)");
final Matcher m = p.matcher(ss);
while (m.find()) {
final String mg = m.group();
if (mg.equals("*") || mg.equals("/") | mg.equals("+") | mg.equals("-")) {
Node node = new Node(mg, new ArrayList<>());
if (root == null) {
root = node;
current = node;
key = node;
} else if (current.left == null) {
current.left = node;
node.parent = current;
key = node;
} else if (current.right == null) {
current.right = node;
node.parent = current;
key = node;
current = current.left;
}
} else if (mg.equals(")")) {
if (current.parent != null) current = current.parent;
key = current;
} else {
key.numbers.add(Integer.valueOf(mg));
}
}
recursive(root);
String o = root.operation;
System.out.println(root.numbers.stream().reduce((a, b) -> operation(a, b, o)).orElse(0));
}
private static void recursive(Node node) {
if (node == null) return;
recursive(node.left);
recursive(node.right);
node.result = node.numbers.stream().reduce((a, b) -> operation(a, b, node.operation)).orElse(0);
if (node != root) node.parent.numbers.add(node.result);
}
private static Integer operation(Integer a, Integer b, String o) {
if (o.equals("+")) return a + b;
if (o.equals("-")) return a - b;
if (o.equals("*")) return a * b;
if (o.equals("/")) return a / b;
return 0;
}
}
class Node {
Node left;
Node right;
Node parent = null;
String operation;
List<Integer> numbers;
Integer result = 0;
public Node(String operation, List<Integer> numbers) {
this.operation = operation;
this.numbers = numbers;
}
}
using System;
public class Test
{
public static void Main()
{
string[] input = new string[]{"(","*","(","+","2","3",")","(","-","5","3","1",")",")"};
foreach(string a in input){
Console.Write(a);
}
Console.WriteLine();
stack(input);
}
static void stack(string[] data){
string[] stk = new string[100];
for(int i=0;i<100;i++){
stk[i]=null;
}
for(int i=0;i<data.Length;i++){
Console.WriteLine("data["+i+"] : "+data[i]);
if(data[i] ==")" ){
Console.WriteLine("pop start");
stk = pop(stk,data[i]);
}else{
stk = push(stk,data[i]);
}
}
Console.WriteLine();
foreach(string b in stk){
Console.Write(b);
}
}
static string[] push(string[] stk,string d){
for(int i=0;i<100;i++){
if(stk[i] == null){
stk[i] = d;
//Console.WriteLine("push : " + stk[i]);
break;
}
}
return stk;
}
static string[] pop(string[] stk,string d){
int sum = 0;
int[] num = new int[10];
string cal = "";
for(int i=0;i<10;i++){
num[i]=0;
}
for(int i=99;i>=0;i--){
// Console.WriteLine("stk : " +stk[i]);
if(stk[i] != null){
if(stk[i] == "("){
Console.WriteLine("cal go");
int cnt = 0;
for(int j = 9;j>=0;j--){
if(num[j]!=0){
sum = num[j];
cnt = j;
Console.WriteLine("cnt : " + cnt);
break;
}
}
for(int j = 0;j<cnt;j++){
if(num[j]!=0){
if(cal == "+"){
sum += num[j];
}else if(cal == "-"){
sum = sum-num[j];
}else if(cal == "*"){
sum *= num[j];
}else{
sum /= num[j];
}
}
}
stk[i]=sum.ToString();
Console.WriteLine("cal_data : " + sum);
Console.Write("stk : ");
foreach(string stkd in stk){
Console.Write(stkd);
}
Console.WriteLine();
break;
}else if(stk[i] =="*" || stk[i] =="/" || stk[i] =="+" || stk[i] =="-"){
Console.WriteLine("cal save" + stk[i]);
cal = stk[i];
stk[i]=null;
}else{
Console.WriteLine("num save");
for(int j = 0;j<10;j++){
if(num[j]==0){
num[j]=Int32.Parse(stk[i]);
stk[i]=null;
Console.WriteLine("pop : " + num[j]);
break;
}
}
}
}
}
return stk;
}
}
def lisp_calc(exp_str):
# 공백을 제거하고 숫자와 기호를순서대로 배열로 만듦
exps = []
for s in exp_str.split(' '):
if s.isdigit():
exps.append(s)
else:
before_num = False
for x in s:
if x.isdigit():
if before_num:
exps.append(exps.pop()+x)
else:
before_num = True
exps.append(x)
else:
exps.append(x)
before_num = False
# 순서대로 파싱하면서 괄호가 닫히면 계산
codes = []
nums = []
begin_bracket = False
for e in exps:
# 괄호가 끝나면 괄호가 닫히기 전 값들을 계산
if e == ')':
exp = codes.pop(-1).join(nums.pop())
res = str(eval(exp))
if len(nums) == 0:
nums.append([res])
else:
nums[-1].append(res)
# 숫자는 nums에 넣음
elif e.isdigit():
if begin_bracket:
nums.append([e])
begin_bracket = False
else:
nums[-1].append(e)
# 괄호가 시작되면 닫히기 전까지 같은 계산식 수준으로 숫자들을 넣도록 마크
elif e == '(':
begin_bracket = True
# 기호
else:
codes.append(e)
return nums[0]
print(lisp_calc('(- 10 3)'))
print(lisp_calc('(* (+ 2 3) (- 5 3))'))
print(lisp_calc('(+ (* 5 2) (- 15 5) (/ 20 2))'))
Python 3으로 풀었습니다. Stack을 이용했는데, 코드 라인수가 좀 길어지네요. 고민을 더 해봐야겠습니다.
def calculate(s):
def is_sign(c):
return c == '*' or c == '-' or c == '+' or c == '/'
def calc(sign, num, others):
if sign == '+': return num + sum(others)
if sign == '-': return num - sum(others)
if sign == '*':
val = num
for x in others:
val *= x
return val
if sign == '/':
val = num
for x in others:
val /= x
return val
return None
if s == '(+)':
return 0
S = []
prev = 0
for c in s:
if c.isdigit():
prev = prev * 10 + int(c)
else:
if prev != 0:
S.append(prev)
prev = 0
if c == '(' or c == ' ':
continue
elif c == ')':
nums = []
while not is_sign(S[-1]):
nums.append(S.pop(-1))
S.append(calc(S.pop(-1), nums[-1], nums[:-1]))
else:
S.append(c)
return S[0]
Python3
원래 개념에 가깝게 해 볼랬는데 딥따 어렵네요..-_-;
E = (+) | (*) | (+ T) | (- T) | (/ T) | N
T = '' | E | T T
N = NN | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
리스트에 해당하는 T = T T 이 부분만 따로 처리했습니다.
tsplit() 함수가 제일 앞의 (리스트가 아닌) term과 나머지 term을 잘라 줍니다.
정규식 썼으면 패턴매칭해서 쉽게 될 듯
계산할 때 eval() 함수를 쓰기 위해 숫자도 전부 문자열로 처리했습니다.
def exp(E):
if E[0] != '(': return E
if E == '(+)': return '0'
if E == '(*)': return '1'
OP, T = E[1], E[3:-1]
return str(eval(OP.join(term(T))))
def term(T):
if T == '': return []
head, tail = tsplit(T)
return [exp(head)] + term(tail)
def tsplit(T):
if T[0] != '(':
p = (T+' ').find(' ')
return T[:p], T[p+1:]
else:
depth = 0
for p in range(len(T)):
depth += (T[p] == '(') - (T[p] == ')')
if depth == 0:
return T[:p+1], T[p+2:]
print(exp('(- 10 3)'))
print(exp('(* 2 3 4)'))
print(exp('(*)'))
print(exp('(/ 10 (*) 5)'))
print(exp('(* (+ 2 3) (- 5 3))'))
print(exp('(/ (+ 9 1) (+ 2 3))'))
print(exp('(* (/ (+ 9 1) (+ 2 3)) 3)'))
# 사람이 계산하는 데로...
# 가장 안 쪽 연산한 결과를 문자열로 대체 후 다시 재귀
def calc(s):
print(s)
p2 = s.find(')') # 처음 찾은 ) 위치
p1 = s.rfind('(', 0, p2) # p2 부터 왼쪽으로 처음 찾은 ( 위치
# 가장 안 쪽 연산
op = s[p1 + 1] # +
sub = s[p1 + 3:p2] # 1 2
sub = sub.replace(' ', op) # 1+2
sub = eval(sub) # 3
if p1 == 0:
return sub
# 연산한 결과를 문자열로 대체 후 다시 재귀
s = s[:p1] + str(sub) + s[p2 + 1:]
return calc(s)
Swift입니다. 재귀호출 없이 풀었습니다.
주어진 수식은 스페이스를 기준으로 문자열 배열로 변환합니다. 변환한 후, 왼쪽에서 오른쪽으로 )를 찾습니다. )를 발견하면 방향을 바꿔 왼쪽으로 (를 찾습니다. 이 때 중첩되지 않은 수식을 발견하게 되며, 계산을 한 후 결과를 발견한 (,) 구간과 바꿔 줍니다.
위 계산을 반복하면 수식이 들어 있던 배열에 최종 결과만 남게 됩니다.
import Foundation
enum CalculationError: Error {
case invalidOperator
case missingOperand
case divideByZero
}
func calculateUnit(_ formula:[String], _ start:Int, _ end:Int) throws -> Int {
let op = formula[start + 1]
if op != "+" && op != "-" && op != "*" && op != "/" {
throw CalculationError.invalidOperator
}
let operandCount = end - start - 2
if (op == "-" || op == "/") && operandCount < 1 {
throw CalculationError.missingOperand
}
let defaultValue = op == "+" ? 0 : 1
var result = (start + 2 < end) ? Int(formula[start + 2])! : defaultValue
var index = start + 3
while index < end {
let value = Int(formula[index])!
switch op {
case "+": result += value
case "-": result -= value
case "*": result *= value
case "/": if value == 0 {throw CalculationError.divideByZero}
result /= value
default: print("Unknown operator - \(op)"); break;
}
index += 1
}
return result
}
func calculate(_ f:String) -> String {
var formula = f.reduce("", {$0 + ($1 == "(" ? "( " : ($1 == ")" ? " )" : String($1))) }).split(separator: " ").map({String($0)})
do {
var closeIndex = 0
while closeIndex < formula.count {
if formula[closeIndex] == ")" {
var openIndex = closeIndex
while openIndex >= 0 {
if formula[openIndex] == "(" {
let result = try calculateUnit(formula, openIndex, closeIndex)
formula.removeSubrange(openIndex...closeIndex)
formula.insert(String(result), at: openIndex)
closeIndex = openIndex
break
}
openIndex -= 1
}
}
closeIndex += 1
}
} catch CalculationError.invalidOperator {
return "Invalid operator"
} catch CalculationError.missingOperand {
return "Operand missed"
} catch CalculationError.divideByZero {
return "Division by Zero"
} catch {
return "Unexpected error: \(error)."
}
return formula[0]
}
print("(- 10 3) = ", calculate( "(- 10 3)"))
print("(- 10 3 5) = ", calculate( "(- 10 3 5)" ))
print("(* 2 3) = ", calculate( "(* 2 3)" ))
print("(* 2 3 4) = ", calculate( "(* 2 3 4)" ))
print("(+) = ", calculate( "(+)" ))
print("(*) = ", calculate( "(*)" ))
print("(* 5) = ", calculate( "(* 5)" ))
print("(- 1) = ", calculate( "(- 1)" ))
print("-5 = ", calculate( "-5" ))
print("(+ 5 -3) = ", calculate( "(+ 5 -3)" ) )
print("(- 5 -3) = ", calculate( "(- 5 -3)" ) )
print("( * ( + 2 3) (- 5 3)) = ", calculate( "(* (+ 2 3) (- 5 3))" ) )
print("( / ( + 9 1) (+ 2 3)) = ", calculate( "(/ (+ 9 1) (+ 2 3))" ) )
print("(-) = ", calculate( "(-)" ))
print("(- 1) = ", calculate( "(- 1)" ))
print("(/) = ", calculate( "(/)" ))
print("(/ 1) = ", calculate( "(/ 1)" ))
print("(/ 1 0) = ", calculate( "(/ 1 0)" ))
print("($ 1 2) = ", calculate( "($ 1 2)" ))
결과는...
(- 10 3) = 7
(- 10 3 5) = 2
(* 2 3) = 6
(* 2 3 4) = 24
(+) = 0
(*) = 1
(* 5) = 5
(- 1) = 1
-5 = -5
(+ 5 -3) = 2
(- 5 -3) = 8
( * ( + 2 3) (- 5 3)) = 10
( / ( + 9 1) (+ 2 3)) = 2
(-) = Operand missed
(- 1) = 1
(/) = Operand missed
(/ 1) = 1
(/ 1 0) = Division by Zero
($ 1 2) = Invalid operator
어렵네요.
아직 코딩 실력이 좋지 않아, 각 예외조항( (+), (*), (/2), -5 등)은 따로 IF 처리했습니다.
그 밖에 연산들은 재귀함수를 이용하여 가장 안의 ()부터 찾고, 찾은것을 계산하여 기존 식에 넣어주는 식으로 재귀를 돌렸습니다.
public class LISP {
public static void main(String[] args) {
String[] temp = { "(- 10 3)", "(- 10 3 5)", "(* 2 3)", "(* 2 3 4)", "(+)", "-5", "(* (+ 2 3) (- 5 3))",
"(/ (+ 9 1) (+ 2 3))", "(*)", "(/ 2)" };
for (int i = 0; i < temp.length; i++)
System.out.println(temp[i] + " -> " + Check(temp[i], temp[i]));
}
private static String Check(String temp, String temp1) {
for (int i = 0; i < temp.length(); i++)
if (temp.charAt(i) == '(')
for (int j = 1; j < temp.length() - 1; j++)
if (temp.charAt(j) == '(')
return Check(temp.substring(j), temp1);
else if (temp.charAt(j) == ')')
return Check(temp1 = temp1.replace(temp.substring(i, j + 1), cal(temp.substring(i, j + 1))),
temp1);
if (!temp.contains("("))
return temp;
return cal(temp);
}
private static String cal(String str) {
if (str.equals("(+)"))
return "0";
if (str.equals("(*)"))
return "1";
String[] temp = str.split(" ");
int num = Integer.valueOf(temp[1].replaceAll("[^0-9]", ""));
if (temp.length > 1)
switch (str.charAt(1)) {
case '+':
for (int i = 2; i < temp.length; i++)
num += Integer.valueOf(temp[i].replaceAll("[^0-9]", ""));
case '-':
for (int i = 2; i < temp.length; i++)
num -= Integer.valueOf(temp[i].replaceAll("[^0-9]", ""));
case '*':
for (int i = 2; i < temp.length; i++)
num *= Integer.valueOf(temp[i].replaceAll("[^0-9]", ""));
case '/':
for (int i = 2; i < temp.length; i++)
num /= Integer.valueOf(temp[i].replaceAll("[^0-9]", ""));
}
return num + "";
}
}
'''
되도록 find 같은 편리한 함수같은거 안쓰고 쌩짜로 짜봤습니다.
'''
def calc_list(l, operator):
if operator == '+':
return sum(l)
elif operator == '-':
v = l[0]
for i in range(1,len(l)):
v -= l[i]
return v
elif operator == '*':
v = l[0]
for i in range(1,len(l)):
v *= l[i]
return v
elif operator == '/':
v = l[0]
for i in range(1,len(l)):
v /= l[i]
return int(v)
else:
return sum(l)
def process_str(s,depth):
s = s.strip()
#print("{}{}".format(' '*depth, s))
depth += 1
if s[0] == '(' and s[len(s) - 1] != ')':
s = s[1:]
if s[0] != '(' and s[len(s) - 1] == ')':
s = s[:-1]
if s[0] == '(' and s[len(s) - 1] == ')':
s = s[1:-1]
l = []
operator = ''
digit = ''
digit_count = 0
open_count = 0
ret = 0
x = -1
for i in range(len(s)):
if i <= x:
continue
if s[i] == '(':
x = i
open_count += 1
while open_count != 0:
x += 1
if s[x] == ')': open_count -= 1
if s[x] == '(': open_count += 1
digit = process_str(s[i:x+1], depth)
l.append(int(digit))
digit_count += 1
digit = ''
elif s[i] in ['+', '-', '*', '/']:
operator = s[i]
elif s[i].isdigit():
digit += s[i]
elif s[i] == ' ':
if digit != '':
#print("{}{}".format(' '*depth, digit))
l.append(int(digit))
digit_count += 1
digit = ''
else:
continue
if digit != '':
#print("{}{}".format(' '*depth, digit))
l.append(int(digit))
digit_count += 1
digit = ''
if digit_count == 0:
return 0
else:
return calc_list(l,operator)
raw_s = input('> ')
depth = 0
v = process_str(raw_s,depth)
print("result : {}".format(v))
import re
def calc(v):
tmp = v.group(1).split()
if tmp[0] == '+' and not tmp[1:]: return '0'
elif tmp[0] == '*' and not tmp[1:]: return '1'
elif not tmp[1:]: raise Exception('{} must have argument'.format(tmp[0]))
elif len(tmp[1:]) == 1: return tmp[1]
else: return str(eval(tmp[0].join(tmp[1:])))
def lispcalc(v):
print(v, end=' → ')
while 1:
if v[0] != '(': break
v = re.sub('\(([+*/-]( [-]?\d+)*?)\)',calc,v)
print(eval(v))
return eval(v)
inp = '''\
(- 3)
(*)
(- 10 3)
(- 10 3 5)
(* 2 3)
(* 2 3 4)
(+)
-5
(* (+ 2 3) (- 5 3))
(/ (+ 9 1) (+ 2 3))'''
[lispcalc(i) for i in inp.split('\n')]
LISP 문법을 몰라서 인자가 하나일때는 그 인자를 반환하게 하였습니다
def LISP(s1):
s2 = list(s1[2:-1])
s1 = [s1[1]]
for x in range(s2.count('(')):
n = ''.join(s2[:s2.index(')')+1][2:-1]).split()
a = n[1]
for x in n[2:]:
a = eval('%s%s%s' %(a,n[0],x))
s1.append(str(a))
del s2[:s2.index(')')+1]
a = s1[1]
for x in s1[2:]:
a = eval('%s%s%s' %(a,s1[0],x))
print(a)
import re
def g(lisp): #lisp가 최소단위일 때
L = re.findall('\d+', lisp)
L = list(map(int, L))
if lisp.find('*') >= 0:
res = 1
for i in range(len(L)): res *= L[i]
return str(res)
if lisp.find('+') >= 0:
res = 0
for i in range(len(L)): res += L[i]
return str(res)
if lisp.find('-') >= 0:
res = L[0]
for i in range(1, len(L)): res -= L[i]
return str(res)
if lisp.find('/') >= 0:
return str(L[0]/L[1])
return 'error' #사칙연산 기호가 없을 때 에러를 반환
def f(lisp):
#괄호의 최소단위를 찾는 정규표현식은 '[(][^(^)]+[)]'
p = re.compile('[(][^(^)]+[)]')
if p.match(lisp): return g(lisp)
return f(p.sub(lambda m : f(m.group()), lisp))
>>> print(f('(* 2 3 4)'))
24
>>> print(f('(* (+ 2 3) (- 5 3))'))
10
>>> print(f('(* (+ (*3 2 1) (+1 2)) (- 5 3))'))
18
>>>
import re
INP, exc = input("INPUT : "), ['(*)', '1', '(+)', '0']
lisp_com = re.compile('\({1}[*+-/]([ ]-?\d*\.?\d+)*\){1}')
KEISAN = re.compile('[*+-/]|[ ]-?\d*\.?\d+')
while lisp_com.search(INP) != None :
if lisp_com.search(INP).group() == '(*)' or lisp_com.search(INP).group() == '(+)' :
INP = lisp_com.sub(exc[exc.index(lisp_com.search(INP).group())+1], INP, count = 1)
else :
TA = lisp_com.search(INP).group()
TA = lisp_com.sub(str(eval('%s' %KEISAN.findall(TA)[0].join(KEISAN.findall(TA)[1:]))), TA, count = 1)
INP = lisp_com.sub(TA, INP, count = 1)
print(INP)
소수점이나 음수의 계산도 가능합니다. (*)와 (+)의 처리 때문에 생각보다는 코드가 길어졌습니다. 아직도 배울게 많네요!
결과
INPUT : (* (+ 2 3) (- 5 3) (*))
10
INPUT : (* (/ (+ 9 1) (+ 2 1 2)) 3 (*))
6.0
def calLISP(s):
if len(s) <= 4:
return 1 if s[1] == '*' else 0
op = s[1]
s = s[3:-1]
lst = [i for i in s.split()]
return str(eval(op.join(lst)))
s = input('LISP 형태로 표현된 4칙연산 산술식: ')
while s[0] == '(':
if len(s) == 3:
s = calLISP(s)
break
lidx = 0
curr = ''
for i, c in enumerate(s):
curr += c
if c == '(' and lidx != -1:
lidx = i
elif c == ')' and lidx != -1:
curr = curr.replace(curr[lidx:], calLISP(s[lidx:i+1]))
lidx = -1
s = curr
print(' -> ', s)