Задача из Амазона

Бродяга · Post by **Бродяга** » 11 Aug 2004 23:19

Write a method (and any supporting classes/methods) that takes as its input a string and returns a value that is the arithmetical evaluation of that string. For example, if the input string is "7 + (5 * 2)", the return value should be 17.

A. Fig Lee · Post by **A. Fig Lee** » 11 Aug 2004 23:27

"польский калькулятор"?

Strannik223 · Post by **Strannik223** » 11 Aug 2004 23:42

A. Fig Lee wrote:"польский калькулятор"?

Так нотация в примере не польская.
Надо ваять синтаксический анализатор. "Книга дракона" должна помочь. Можно конечно в лоб решать эту задачу, разбирать скобки посимвольно, итд, но подозреваю что хотят видеть именно синтаксическй анализатор. Долго описывать, кому интересно смотите по поводу теории компиляторов.

Nervous · Post by **Nervous** » 12 Aug 2004 00:45

Strannik223 wrote:
Так нотация в примере не польская.
Надо ваять синтаксический анализатор. "Книга дракона" должна помочь. Можно конечно в лоб решать эту задачу, разбирать скобки посимвольно, итд, но подозреваю что хотят видеть именно синтаксическй анализатор. Долго описывать, кому интересно смотите по поводу теории компиляторов.

Думаю, Странник прав. Есть смысл еще знать что такое "машина конечных состояний" (final state machine) или, как их еще называют - "конечные автоматы".

ven27 · Post by **ven27** » 12 Aug 2004 01:24

Nervous wrote:... "машина конечных состояний" (final state machine) или, как их еще называют - "конечные автоматы".

таки Finite State Machine :wink:

Nervous · Post by **Nervous** » 12 Aug 2004 01:32

ven27 wrote:
Nervous wrote:... "машина конечных состояний" (final state machine) или, как их еще называют - "конечные автоматы".

таки Finite State Machine

OK!

111001 · Post by **111001** » 12 Aug 2004 02:15

Бродяга wrote:Write a method ...

Раз язык не задан, возьмем любой с eval() ;-)

Например, javascript:

Code: Select all

function reshenie_zadachi(str)
{
 try
 { return eval(str);
 }
 catch(e) { return "Error in expression"; }
}

Интересно также, что они не определили какие формулы допустимы.
Ожидают +-*/ калькулятора на 30 строчек на Java, не иначе.
Html test:

Code: Select all

<HTML>
<HEAD>
<SCRIPT LANGUAGE="JavaScript">
function reshenie_zadachi(str)
{ try
  { return eval(str); }
  catch(e) { return "Error in expression"; }
}
function do_calc(form)
{ form.result.value = reshenie_zadachi(form.formula.value);
}
</SCRIPT>
</HEAD>
<BODY>
<CENTER>
<FORM name="myform">Formula: <input type="text" size="80" name="formula">
<input type="button" value="  Calculate " onClick="do_calc(this.form)">
<p>Result = <input type="text" name="result" size="80">
</FORM>
</CENTER>
</BODY>
</HTML>

Strannik223 · Post by **Strannik223** » 12 Aug 2004 02:23

111001: Юмор оценен :mrgreen:

А вы говорите конечные автоматы :lol:

Mongush · Post by **Mongush** » 12 Aug 2004 02:27

Хе-хе, это пример из Страуструпа.
Да и так ничего сложного там нет, на полчаса-час работы максимум.

katit · Post by **katit** » 12 Aug 2004 02:27

У нас в школе на олимпиаде такая была.
Только eval() небыло.

Если писать то получится ничего так. С рекурсией и прочее

WildVlad · Post by **WildVlad** » 12 Aug 2004 03:41

katit wrote:У нас в школе на олимпиаде такая была.
Только eval() небыло.

Если писать то получится ничего так. С рекурсией и прочее

По-моему даже выражение со скобками разбирается без рекурсии.

Кстати, если язык Java, а у Бродяги именно он, то есть очень лёгкое решение, тербуещее присутсвия JDK (JRE is not enough), а именно сгенерить сырец класса на Java, потом откомпилить это, подгрузить своим ClassLoader'ом, выполнить, а потом убить нафиг ClassLoader вместе со всеми классами, которые он подгрузил

Сразу на халяву автоматом сработают все допустимые в Java выражения и функции и даже операторы

Strannik223 · Post by **Strannik223** » 12 Aug 2004 04:08

Да, тут непонятно какого характера задача, прикладная, то есть можно "мошенничать" или тестовая, то есть надо показать что ты умные книжки по компиляторам читал и даже что то помнишь.

hooch · Post by **hooch** » 12 Aug 2004 04:15

http://forum.java.sun.com/thread.jsp?fo ... ge=1667337

Бродяга · Post by **Бродяга** » 12 Aug 2004 04:52

Задача тестовая. Позвонили, прислали мейл. Дали 1 час на работу. Через час перезвонили и сказали давай результат. В общем результат выдал. Нашел хорошее описание алгоритма, по нему написал код.
В общем вначале перевожу обычную строку в postfix а из postfix потом уже считаю результат. Посмотрим что завтра скажут:-) Спросили что я думаю по поводу этого задания. Сказал что оно простое для тех кто умеет пользоваться гуглом или имеет книгу с алгоритмами под рукой, для тех кто занимается кодингом business logic, EJB, Database то это занятие будет тяжёлым. Поэтому считаю что это конкретное задание не показывает то что человек знает. Ну потом были обычные вопросы - что ты хочешь а что нет, сильные и слабые стороны и т.д. Сказали что у них более сотни позиций и людей не хватает. Ездят в канаду за ними. Новые H1 не делают вообще. Трансфер делают и ГК делают. Понравилось то, что звонили по нормальной линии и очень хорошо всё слышал.

Yuri Khupchenko · Post by **Yuri Khupchenko** » 13 Aug 2004 08:30

Чем закончилось-то? Лично мне кажется, что они ожидали увидеть recursive-descent parser.

Привет

Задача из Амазона

Задача из Амазона

Re: Задача из Амазона