ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1101. Robot in the Field

Easy task
Posted by AXIS 9 Jan 2007 16:36
Evaluation of this expression isn't a problem :

1) Replace all of operators into one-char operators. For example, NOT into '-', TRUE into '1', etc.
It will greatly simplify coding, because of operators don't begin on char, that can be a register.

2) Recursive descent :
In function we've got bounds of the expression and we'll find result of it in this bounds.
Find the least priority operator first. This is an operator, that has least number of not closed brackets, and if we find operator with equal number of such brackets the least in priority of operators.
Then : if not found any operator, then expression has only register or constant. Calculate it.
if NOT - Result = not Evaluate(pos_of_operator, right bound),
if OR or AND - Result = Evaluate(left_bound, pos_of_operator - 1) OPERATOR Evaluate(pos_of_operator + 1, right_bound) (crazy pseudocode =) )

That's all. Of course, it's a slow method, but it's very easy - without any problems, debugging or testing i've got fast AC 0.015 sec, 300kb
Re: Easy task
Posted by Kit 20 Jan 2007 21:18
Thank you very much!
I really hate such problems, but your ideas make it much easier!
Thanks!
Re: Easy task
Posted by GaLL [fac. of philology Tyumen SU] 21 Jan 2007 03:09
Why do you hate such a problems? There is some enchantment in parsers, imho.
Re: Easy task
Posted by Kit 21 Jan 2007 19:15
May be, I just don't know right way to deal with parsers... Anyway, such tasks always offer a great problem for me.
Re: Easy task
Posted by AXIS 6 Feb 2007 00:32
Parsers is my element)
If you need other technical help - i'm at your service)
Re: Easy task
Posted by [Ural SU] GetTester 15 Jul 2008 02:13
AXIS - *LOL*