Code contest 2

[Browni3141]

I'll start this right now. I've got a good idea on how to process the parenthesis.

P.S. What do we get for winning? Eternal glory perhaps?

[Duthomhas]

I really think we ought to keep it to C++.
In Tcl it would be much like Ruby: puts [expr [gets stdin]], which defeats the point...

[chrisname]

He did say not to use built-in eval() style functions...

Btw I'm not good enough at Haskell to do this yet, so I probably won't be entering unless I learn Haskell properly in time, which is unlikely given the exams I have coming up and the fact I'm already trying to get cgl to work before the 11^th.

[ne555]

rapidcoder wrote:

"It must not support anything besides this" rule - which was added just to rule out all the "my language has a function that does that" solutions, which would not be interesting at all.

Well, you could make sure to follow the "anything besides this" rule and use eval.

@Duoas: what is the point? xP
Maybe you could try to program the expr function (but still, which will be the limit of what you could use?)

Edit: I know, let's limit it to brainfuck!

[chrisname]

@ne55,
That's not even funny, brainfuck is horrible to use (although some people actually wrote optimising brainfuck compilers in brainfuck which is insane).

[Duthomhas]

Yes, but I could tell Tcl which mathops expr will allow...

[m4ster r0shi]

Ok, here's mine:

import scala.util.parsing.combinator._
import scala.math._ //for pow

class AwesomeArithmeticParser extends JavaTokenParsers {

    val op_table: Map[String,(Double,Double) => Double] =
        Map("+" -> (_+_), "-" -> (_-_), "*" -> (_*_),
                "/" -> (_/_), "^" -> (pow(_,_)) )

    //( n, ((op1,n1), (op2, n2), (op3, n3), ...) ) --->
    // ---> (((n op1 n1) op2 n2) op3 n3) ...
    def fold(n: Double, l: List[~[String,Double]]) =
        l.foldLeft(n){ case (n1,op~n2) => op_table(op)(n1,n2) }

    //the type for expression is needed because it's called recursively
    def expression: Parser[Double] =
        term~((("+"|"-")~term)*) ^^ { case h~t => fold(h,t) }

    def term = factor~((("*"|"/")~factor)*) ^^ { case h~t => fold(h,t) }

    def factor = primary~(("^"~primary)*) ^^ { case h~t => fold(h,t) }

    //parentheses should/need not appear in the parse tree
    def primary = number|("("~>expression<~")")

    def number = floatingPointNumber ^^ { _.toDouble }

    def eval(exp: String) = parseAll(expression,exp)
}

object MyApp extends Application {

    var my_parser = new AwesomeArithmeticParser
    var input = readLine

    while (input != "") {
        println(my_parser.eval(input))
        input=readLine
    }
}

EDIT: Pattern matching FTW!!! :D

[kfmfe04]

@m4ster r0shi

beautiful!

will have to try it out later!
btw, does it implement the error handling requirement properly?

[helios]

Supports +, - (both binary and unary), /, *, ^, (), correct precedence and associativity, error checking (but doesn't say what the error is), and four types of literals: '#', '.#', '#.', and '#.#'.

For an explanation of the algorithm, see http://www.cplusplus.com/forum/lounge/11845/#msg56388

#include <cctype>
#include <cstdarg>
#include <cmath>
#include <iostream>
#include <sstream>
#include <vector>

template <typename T2,typename T>
T2 ato(const std::basic_string<T> &str){
	std::basic_stringstream<T> stream(str);
	T2 res;
	return !(stream >>res)?0:res;
}

template <typename T> inline long atol(const std::basic_string<T> &str){ return ato<long>(str); }
template <typename T> inline double atof(const std::basic_string<T> &str){ return ato<double>(str); }

struct Accumulator;

enum TokenType{
	null=0,
	END=1,
	INTEGER='0',
	POINT='.',
	PLUS='+',
	MINUS='-',
	MUL='*',
	DIV='/',
	POW='^',
	LPAREN='(',
	RPAREN=')',
	expr=128
};

struct Token{
	TokenType type;
	double f_value;
	std::string literal;
	Token(TokenType type=END):type(type),f_value(0){}
	Token(const std::string &val):type(INTEGER),literal(val){}
	Token(char character){
		this->type=(TokenType)character;
	}
	Accumulator operator<<(const Token &);
};

struct Rule;

typedef Token (*handler_f)(const Rule &,const Token *);

struct Accumulator{
	int state;
	Token reduces_to,
		lookahead;
	std::vector<Token> constraints;
	handler_f handler;
	Accumulator(const Token &token):state(0),handler(0){
		this->reduces_to=token;
	}
	Accumulator &operator<<=(const Token &token){
		if (!this->state){
			this->lookahead=token;
			state++;
		}else
			this->constraints.push_back(token);
		return *this;
	}
	Accumulator operator<<(const Token &token){
		Accumulator r=*this;
		r<<=token;
		return r;
	}
	Accumulator &operator<<=(const handler_f f){
		this->handler=f;
		return *this;
	}
	Accumulator operator<<(const handler_f f){
		Accumulator r=*this;
		r<<=f;
		return r;
	}
};

Accumulator Token::operator<<(const Token &token){
	return Accumulator(*this)<<token;
}

struct Rule{
	Token reduces_to;
	std::vector<Token> constraints;
	Token lookahead;
	handler_f handler;
	Rule(const Accumulator &accum):
		reduces_to(accum.reduces_to),
		lookahead(accum.lookahead),
		constraints(accum.constraints),
		handler(accum.handler){}
	bool matches(const std::vector<Token> &stack,const Token &lookahead){
		if (stack.size()<this->constraints.size() ||
				this->lookahead.type!=null && this->lookahead.type!=lookahead.type)
			return 0;
		const Token *array=&stack[stack.size()-this->constraints.size()];
		for (unsigned a=0,size=this->constraints.size();a<size;a++)
			if (array[a].type!=this->constraints[a].type)
				return 0;
		return 1;
	}
};

double make_fractional_part(const std::string &str){
	double r=0;
	for (size_t a=0;a<str.size();a++){
		r+=(str[str.size()-a-1]-'0');
		r/=10;
	}
	return r;
}

#define DEFINE_HANDLER(x,y)                               \
	Token x(const Rule &rule,const Token *redex){         \
		Token new_token(rule.reduces_to);                 \
		y;                                                \
		return new_token;                                 \
	}

DEFINE_HANDLER(
	handle_int_p_int,
	new_token.f_value=atof(redex[0].literal)+make_fractional_part(redex[2].literal)
)
DEFINE_HANDLER(
	handle_p_int,
	new_token.f_value=make_fractional_part(redex[1].literal)
)
DEFINE_HANDLER(
	handle_int,
	new_token.f_value=atof(redex[0].literal)
)
DEFINE_HANDLER(
	handle_nop,
	new_token.f_value=redex[1].f_value
)
DEFINE_HANDLER(
	handle_minus_int,
	new_token.f_value=-redex[1].f_value
)
DEFINE_HANDLER(
	handle_pow,
	new_token.f_value=pow((double)redex[0].f_value,(double)redex[2].f_value)
)
DEFINE_HANDLER(
	handle_mul,
	new_token.f_value=redex[0].f_value*redex[2].f_value
)
DEFINE_HANDLER(
	handle_div,
	new_token.f_value=redex[0].f_value/redex[2].f_value
)
DEFINE_HANDLER(
	handle_add,
	new_token.f_value=redex[0].f_value+redex[2].f_value
)
DEFINE_HANDLER(
	handle_sub,
	new_token.f_value=redex[0].f_value-redex[2].f_value
)

class Parser{
	std::stringstream stream;
	std::vector<Token> stack;
	bool result;
	std::vector<Rule> rules;
	Token read(){
		char character;
		while (!this->stream.eof() && isspace(character=this->stream.peek()))
			this->stream.get();
		if (this->stream.eof())
			return END;
		character=this->stream.peek();
		if (isdigit(character)){
			std::string str;
			str.push_back(this->stream.get());
			while (isdigit(this->stream.peek()))
				str.push_back(this->stream.get());
			return str;
		}
		return (char)this->stream.get();
	}
	bool reduce(const Token &lookahead){
		long rule_index=-1;
		unsigned max=0;
		for (unsigned a=0;a<this->rules.size();a++){
			if (this->rules[a].matches(this->stack,lookahead) && this->rules[a].constraints.size()>max){
				rule_index=a;
				max=this->rules[a].constraints.size();
			}
		}
		if (rule_index<0 || this->rules[rule_index].reduces_to.type==null)
			return 0;
		Rule &rule=this->rules[rule_index];
		Token new_token=rule.handler(rule,&this->stack[this->stack.size()-rule.constraints.size()]);
		for (unsigned a=0;a<rule.constraints.size();a++)
			this->stack.pop_back();
		this->stack.push_back(new_token);
		return 1;
	}
	bool run(){
		Token next_token=this->read();
		while (this->reduce(next_token));
		switch (next_token.type){
			case END:
				this->result=(this->stack.size()==1);
				return 0;
			case INTEGER:
			case POINT:
			case PLUS:
			case MINUS:
			case MUL:
			case DIV:
			case RPAREN:
			case LPAREN:
			case POW:
				this->stack.push_back(next_token);
				return 1;
			default:
				this->result=0;
				return 0;
		}
	}
	void initialize_rules(){
		this->rules.clear();
#define DEFINE_RULE(x,y,z) this->rules.push_back(Rule(Token(x) << y << z))
		DEFINE_RULE(null,POINT,INTEGER);
		DEFINE_RULE(null,INTEGER,INTEGER << POINT);
		DEFINE_RULE(expr,null,INTEGER << POINT << INTEGER << handle_int_p_int);
		DEFINE_RULE(expr,null,INTEGER << POINT << handle_int);
		DEFINE_RULE(expr,null,POINT << INTEGER << handle_p_int);
		DEFINE_RULE(expr,null,INTEGER << handle_int);
		
		DEFINE_RULE(expr,null,LPAREN << expr << RPAREN << handle_nop);
		
		DEFINE_RULE(expr,null,PLUS << expr << handle_nop);
		DEFINE_RULE(expr,null,MINUS << expr << handle_minus_int);
		
		DEFINE_RULE(null,POW,expr << POW << expr);
		DEFINE_RULE(expr,null,expr << POW << expr << handle_pow);
		
		DEFINE_RULE(null,POW,expr << MUL << expr);
		DEFINE_RULE(expr,null,expr << MUL << expr << handle_mul);
		
		DEFINE_RULE(null,POW,expr << DIV << expr);
		DEFINE_RULE(expr,null,expr << DIV << expr << handle_div);
		
		DEFINE_RULE(null,POW,expr << PLUS << expr);
		DEFINE_RULE(null,MUL,expr << PLUS << expr);
		DEFINE_RULE(null,DIV,expr << PLUS << expr);
		DEFINE_RULE(expr,null,expr << PLUS << expr << handle_add);
		
		DEFINE_RULE(null,POW,expr << MINUS << expr);
		DEFINE_RULE(null,MUL,expr << MINUS << expr);
		DEFINE_RULE(null,DIV,expr << MINUS << expr);
		DEFINE_RULE(expr,null,expr << MINUS << expr << handle_sub);
	}
public:
	Parser(){
		this->initialize_rules();
	}
	bool eval(double &res,const std::string &str){
		this->stream.str(str);
		this->stream.clear();
		this->stack.clear();
		this->result=0;
		while (this->run());
		if (this->result)
			res=this->stack.front().f_value;
		else
			this->stack.clear();
		return this->result;
	}
};

int main(){
	Parser evaluator;
	while (1){
		double res=0;
		std::string input;
		std::getline(std::cin,input);
		if (!input.size())
			break;
		if (evaluator.eval(res,input))
			std::cout <<"ACCEPT\n="<<res<<std::endl;
		else
			std::cout <<"REJECT\n";
	}
	return 0;
}

[m4ster r0shi]

kfmfe04 wrote:

btw, does it implement the error handling requirement properly?

Yes, it detects errors and says what the error is.

[chrisname]

I'll try in Python, then... without using eval() :)

[Duthomhas]

[edit] This version has a bug, as noted by Helios. See below for the corrected version. [/edit]

Pure C++

/*
  Standard Recursive-Descent Expression Calculator, conforming to contest at
  http://www.cplusplus.com/forum/lounge/42426/

  Copyright 2010 Michael Thomas Greer

  I presume that you will not tokenize on #include directives... which gives
  me a token count of 352 (give or take, as I counted quickly by eye).

  The unary negation operator costs 15 tokens. (define UNARY_NEGATION)
  Negative numbers only costs 7 tokens.        (define NEGATIVE_NUMBERS)
  (If you define the first then you do not need to define the second.)

  Certain error checks (such as division by zero) were not included in the
  interest of brevity, as permitted by the contest rules. Likewise, it should
  be noted that "0^0" returns "1", which is technically incorrect, but the
  result given by the CPU.
*/
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdlib>
#include <functional>
#include <iostream>
#include <string>
using namespace std;

typedef const char* pchar;

double value( pchar& sp )
  {
  double expression( pchar& );

  #ifdef UNARY_NEGATION
  if (*sp == '-')
    return -value( ++sp );
  #endif

  if (isdigit( *sp )
    #ifdef NEGATIVE_NUMBERS
      || (*sp == '-')
    #endif
    )
    return strtod( sp, (char**)(&sp) );

  if (*sp != '(') throw 1;
  double result = expression( ++sp );
  if (*sp != ')') throw 1;
  ++sp;

  return result;
  }

double factor( pchar& sp )
  {
  double result = value( sp );
  while (*sp && (*sp == '^'))
    result = pow( result, value( ++sp ) );
  return result;
  }

double term( pchar& sp )
  {
  double result = factor( sp );
  while (true)
    switch (*sp)
      {
      case '*': result *= factor( ++sp ); break;
      case '/': result /= factor( ++sp ); break;
      default:  return result;
      }
  }

double expression( pchar& sp )
  {
  double result = term( sp );
  while (true)
    switch (*sp)
      {
      case '+': result += term( ++sp ); break;
      case '-': result -= term( ++sp ); break;
      default:  if (*sp && (*sp != ')')) throw 1;
                else return result;
      }
  }

int main()
  {
  string s;
  while (getline( cin, s ))
    try
      {
      s.erase(
        remove_if( s.begin(), s.end(), ptr_fun <int, int> ( isspace ) ),
        s.end()
        );
      pchar sp = s.c_str();
      cout << expression( sp ) << "\n";
      }
    catch (...)
      {
      cout << "error\n";
      }
  }

I've tested it sufficient to my interest, but not sufficient to industrial use... In general, nearly everything that is not valid should print "error". (The only possible exception I am aware of is when unary negation is enabled then it is possible to enter "4---3" to get "1".)

Now I might go do it in Tcl, which should prove much smaller...

[edit] JSYK, the unary negation stuff was thrown-in last minute... I didn't give it much thought but the negation seems to work either way...

[helios]

Unmatched closing parentheses are not rejected.

[chrisname]

The only thing mine rejects at the moment is unmatched parentheses :)

[Duthomhas]

Argh! I didn't think of that...

Give me a short bit and I'll fix it.

------

OK, here you go.

/*
  Standard Recursive-Descent Expression Calculator, conforming to contest at
  http://www.cplusplus.com/forum/lounge/42426/

  Copyright 2010 Michael Thomas Greer

  I presume that you will not tokenize on #include directives... which gives
  me a token count of 373 (give or take, as I counted quickly by eye).

  Certain error checks (such as division by zero) were not included in the
  interest of brevity, as permitted by the contest rules. Likewise, it should
  be noted that "0^0" returns "1", which is technically incorrect, but the
  result given by the CPU.

  This is the repaired version, fixing the parentheses mismatch error pointed
  out by Helios. (Thanks!) Notice the use of a global variable, as this is
  shorter on tokens. :->
*/
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdlib>
#include <functional>
#include <iostream>
#include <string>
using namespace std;

typedef const char* pchar;

unsigned pcount;

double value( pchar& sp )
  {
  double expression( pchar& );

  if (isdigit( *sp ) || (*sp == '-'))
    return strtod( sp, (char**)(&sp) );

  if (*sp != '(') throw 1;
  ++pcount;
  double result = expression( ++sp );
  if (*sp != ')') throw 1;
  --pcount;
  ++sp;

  return result;
  }

double factor( pchar& sp )
  {
  double result = value( sp );
  while (*sp && (*sp == '^'))
    result = pow( result, value( ++sp ) );
  return result;
  }

double term( pchar& sp )
  {
  double result = factor( sp );
  while (true)
    switch (*sp)
      {
      case '*': result *= factor( ++sp ); break;
      case '/': result /= factor( ++sp ); break;
      default:  return result;
      }
  } 

double expression( pchar& sp )
  {
  double result = term( sp );
  while (true)
    switch (*sp)
      {
      case '+': result += term( ++sp ); break;
      case '-': result -= term( ++sp ); break;
      default:  if (!*sp || (pcount && (*sp == ')'))) return result;
                throw 1;
      }
  } 

int main()
  {
  string s;
  while (getline( cin, s ))
    try
      {
      pcount = 0;
      s.erase(
        remove_if( s.begin(), s.end(), ptr_fun <int, int> ( isspace ) ),
        s.end()
        );
      pchar sp = s.c_str();
      cout << expression( sp ) << "\n";
      }
    catch (...)
      {
      cout << "error\n";
      }
  }

I'm still not sure why the unary negation works... but I'll just bite the seven-token bullet and leave it in.

[Abramus]

Python:

import re
while True:
   try:
      s = raw_input()
      if s != re.compile('([-+*/^() ]|([0-9]+(\\.[0-9]*)?([Ee][+-]?[0-9]+)?)|(\\.[0-9]+([Ee][+-]?[0-9]+)?))+').match(s).group():
         raise Exception
      print eval(re.compile('\\^').sub('**', s))
   except:
      print 'error'

Yep, my program uses eval and yet conforms to the "It must not support anything besides this" rule thanks to regular expressions. Feel free to reject my program from the contest if you consider this cheating:)

[ne555]

Does reject input like 3**2?

Edit: How I quit from the program?
Edit2: Also input () (any number of nested parenthesis) -> output ().

[Abramus]

You are right, I didn't reconsider my program well. Of course all these issues can be easily fixed, but I won't bother, partially because this was supposed to be a joke not a serious attempt, and partially because we don't have a judge anymore.

[Abramus]

This thread seems to be dead now, what is a shame as was quite interesting. Anyway, I had some free time recently and I decided to try to beat m4ster r0shi's attempt, without cheap tactics like eval this time. Not sure if I succeeded, but I just cannot think of any way to make it shorter. Of course this program is optimized for length, not efficiency:)

import re

num_ptrn = r'[ ]*([-+]?(?:[0-9]+(?:\.[0-9]*)?(?:[Ee][+-]?[0-9]+)?|\.[0-9]+(?:[Ee][+-]?[0-9]+)?))[ ]*'

def reduce_op(str, chr, set, fun):
   m = re.search(r'(?:(?<=' + set + r')|^)' + num_ptrn + chr + num_ptrn + r'(?:(?=' + set + r')|$)', str)
   if m != None:
      str = str[:m.start(1)] + repr(fun(float(m.group(1)), float(m.group(2)))) + str[m.end(2):]
   return str

while True:
   str = raw_input()
   while True:
      tmp = re.sub(r'\(' + num_ptrn + r'\)', r'\1', str)
      tmp = reduce_op(tmp, r'\^', r'[-+*/^()]', lambda x, y: x ** y)
      tmp = reduce_op(tmp, r'\*', r'[-+*/()]',  lambda x, y: x * y)
      tmp = reduce_op(tmp, r'\/', r'[-+*/()]',  lambda x, y: x / y)
      tmp = reduce_op(tmp, r'\+', r'[-+()]',    lambda x, y: x + y)
      tmp = reduce_op(tmp, r'\-', r'[-+()]',    lambda x, y: x - y)
      if tmp == str:
         m = re.match(num_ptrn, tmp)
         if m != None and m.group(1) == tmp:
            print tmp
         else:
            print 'error'
         break
      str = tmp

[Mathhead200]

Here's my submission:

#Perl Calculator
#Author: Christopher D'Angelo
#Last Modified: May 12, 2011

$\ = "\n";
$pos_num = '([\d]+|[\d]*\.[\d]+)';
$num = "([-+]?$pos_num)";
$term = "\\(($num([\D]+$num)?)\\)";

sub calc {
	my($_, $x) = ($_[0], $_[0]);
	while(/$term/) { my $ans = &calc($1); s/$term/$ans/; }
	while(/$num\^$num/) { my $ans = $1 ** $3; s|$num\^$num|$ans|; }
	while(/$num\*$num/) { my $ans = $1 * $3; s|$num\*$num|$ans|; }
	while(/$num\/$num/) { my $ans = $1 / $3; s|$num/$num|$ans|; }
	while(/$num\+$num/) { my $ans = $1 + $3; s|$num\+$num|$ans|; }
	while(/$num-$num/) { my $ans = $1 - $3; s|$num-$num|$ans|; }
	return &calc($_) if( $_ ne $x );
	$_;
}

my $_ = <STDIN>;
s/-($pos_num\^.+)/-1*(\1)/g;
s/\s+//g;
$_ = &calc($_);
if(/^$num$/) { print; }
else { print 'error'; }