Калькулятор с использованием 2 стеков

У меня есть назначение сборки Intel. Мне нужно написать калькулятор, который использует 2 стека. Например, у меня есть выражение вроде 23 + 4/2 ^ 4 $. Так что $ указывает на конец выражения. Я сделаю два стека, один для чисел, один для операторов, и вытолкну и вытолкну их в соответствии с приоритетом оператора.

Что мне нужно, так это как я могу использовать 2 стека для двух разных целей одновременно. Насколько я знаю, регистр esp указывает место для переменных в стеке, чтобы выталкивать последние или выдвигать новые. Но если у меня только один регистр esp, как я могу иметь два стека?

Заранее спасибо...

13.12.2008 21:31:52
6 ОТВЕТОВ

Я думаю, что вы ищете алгоритм шунтирования Дейкстры.

Я решил это без использования стеков во время интерпретации, только во время выполнения, как описано в моем блоге.

Что касается создания дополнительных стеков, это довольно просто. Весь стек - это просто область памяти с указателем сверху и снизу. Каждый раз, когда вы нажимаете, вы увеличиваете верхний указатель, каждый раз, когда вы нажимаете, уменьшаете верхний указатель.

4
13.12.2008 21:37:35

Поскольку ваши два стека не являются независимыми, другой идеей будет чередование данных в одном стеке . Например, вы могли бы использовать четные слова для чисел и нечетные слова для операторов.


Редактировать: развивая идею в соответствии с просьбой в комментарии: я считаю, что каждый раз, когда вы нажимаете оператор, вы затем нажимаете число, следующее за ним (потому что за этим номером в свою очередь может следовать оператор более высокого приоритета). Точно так же, каждый раз, когда вы используете pop и operator, вы собираете два операнда и выдвигаете результат. Таким образом, стек операторов и стек операндов растут и уменьшаются в тандеме, и, поскольку первоначальный вопрос заключался в том, как сделать это в коде сборки, я предложил, чтобы они могли совместно использовать чередующиеся слоты в одном стеке. (Если этого недостаточно, пожалуйста, дайте мне знать, и я буду редактировать снова.)

0
13.12.2008 22:34:55
Я думаю, что это очень интересная идея, которая нуждается в разработке.
Guge 13.12.2008 22:07:29
чередование стеков ... эта хитрость доставит вам неприятности
xxxxxxx 14.12.2008 09:47:43
Если OP реализует это как RPN, то операторы и операнды не будут чередовать 1: 1. Например, 5 * (6 - 3) будет {6,3, -, 5, } или даже {5,6,3, -, }, что, как я думаю, генерирует алгоритм маневрового двора.
P Daddy 14.12.2008 19:31:36

Или вы можете сделать это самым простым способом, который мог бы работать ™, и реализовать оба стека выполнения в памяти; как указано выше, вам нужен только указатель TOP и некоторая арифметика.

2
13.12.2008 22:19:43

Итак, я прав, чтобы создать два стека, как это:

mov ecx,256
L1: call ReadInt
    push eax          ;push the integer to where esp=1 points
    add esp,ecx       ;esp=1+256=257, now esp points to 257.

    call ReadChar     ;read operand
    cmp al,endChar    ;compare with end sign=$
    je next       
    push al           ;push operand to where esp=257 points
    sub esp,ecx       ;esp=257-256=1, now esp is in the original position
    loop L1
next:
...

Конечно, комментарии для первого цикла.

Кстати, я получил сообщение "1> .. \ main.asm (46): ошибка A2149: регистр байтов не может быть первым операндом" ошибка (push al)? в чем дело?

Спасибо...

-1
13.12.2008 22:47:27
У вас возникнут проблемы, если произойдет прерывание между «add esp, ecx» и «sub esp, ecx». Вместо этого вам придется поддерживать два указателя на свои стеки. Один может быть ESP, другой должен быть EBP.
P Daddy 14.12.2008 19:24:30
Что касается вашей ошибки («регистр байтов не может быть первым операндом»), вам придется нажать eax, а не al. Вы можете выдвигать только регистры полной ширины. esp всегда должен быть выровнен по границе машинного слова.
P Daddy 14.12.2008 19:26:24

Предположим, что выражение имеет длину L, тогда каждый из ваших стеков будет максимум L, поэтому вам потребуется максимум 2L памяти.
увеличьте ESP на 2 л, в ESP у вас будет начало вашего первого стека, в ESP + L у вас будет начало вашего второго стека (следует отметить, что ни один из этих стеков никогда не превысит L, поскольку выражение имеет длину л).
Алгоритм маневрового двора можно найти в разных местах. Он выполняет преобразование из инфиксной записи
в постфиксную запись. После этого оценка постфиксной нотации не составит труда.

Редактировать: также, для манипулирования двумя стеками, вам нужно где-то хранить указатели их стеков.
Для этого вы можете использовать 2 регистра по вашему выбору, например, EBX, ECX,
чтобы один имел значение ESP, а другой - ESP + L. Каждый раз, когда вы будете использовать один или другой стек, вам придется обновлять ESP с помощью соответствующего EBX или ECX или где угодно, где вы можете хранить свои 2 указателя стека, потому что push и pop изменят ESP, и вы захотите, чтобы они изменили версию ESP, которая нужен, а не другой. Также, когда вы закончили pop / push, вы должны обновить EBX / ECX со значениями ESP.

0
14.12.2008 22:41:35

Все эти ответы предполагают, что не существует такой вещи, как приоритет оператора. Очевидно, что использование стеков, упомянутых в вопросе, намекает на правильный ответ, связанный с вычислениями, использующими приоритет операторов.

Вот ссылка, которая объясняет, чего вы пытаетесь достичь. http://epaperpress.com/oper/index.html

1
13.12.2008 23:28:43
«Все эти ответы предполагают, что не существует такой вещи, как приоритет оператора»? Какая ? Откуда вы взяли этот вывод?
xxxxxxx 14.12.2008 09:30:53
Эта проблема является известной проблемой приоритета операторов и решается известной системой обозначений Infix. Ответы выше, кажется, не принимают во внимание стеки и говорят об удалении стеков, что убивает цель вышеприведенного упражнения.
fasih.rana 15.12.2008 11:04:33
Я думаю, что вы не знаете, о чем говорите
xxxxxxx 10.03.2010 08:21:19