The program must translate algebraic expression into a list of commands in assembly language.

An algebraic expression may contain lowercase and uppercase letters, as well as "+", "-", "*", "/", "(", ")". Example: "A + Bc * (aB)"

The computer has 10 registers - memory cells (R0..R9) and one adder. Each command in the sequential list of commands begins with a new line and contains the command code itself (I will describe the commands below) and, after the space, the operand (the variable name or register). Commands:

Команда: L операнд Смысл: сумматор := операнд Команда: A операнд Смысл: сумматор := сумматор + операнд Команда: S операнд Смысл: сумматор := сумматор - операнд Команда: M операнд Смысл: сумматор := сумматор * операнд Команда: D операнд Смысл: сумматор := сумматор / операнд Команда: ST регистр Смысл: регистр := сумматор

There are two files: input.txt and output.txt

input.txt contains the algebraic expression itself (no more than 100 characters), which can be calculated using no more than 10 registers.

output.txt must contain a sequence of assembler language commands, as a result of which the resulting value is placed in the adder. The assembler program must contain all the operations of the expression (without saving operations).

Example: input.txt

 A*BC*(B+X)

output.txt

 LA или LB MBAX ST R0 MC LB ST R1 AXLA ST R1 MB LCS R1 M R1 ST R1 L R0 S R1

I understood the very meaning of the task, but I don’t even know how to start it. Based on the example, most likely, you need to start with a search for opening parentheses, perform lower priority operations first, but which data structures are better to use and the solution algorithm itself is not yet clear.

  • one
    Read about the reverse Polish entry. There are even examples of algolist.manual.ru/syntax/revpn.php Although I personally am not very familiar with it and probably would have followed the path of passing through the line with the prioritization of operators, adding some "basic priority" that would increase, say, 10 for each ( and decreasing when ) And then went through in the order of decreasing priorities, capturing the operands to the left and right of the operation and building the execution tree - Mike
  • About parsing arithmetic expressions is a good chapter in the book by Robert Lafore, "Data Structures and Algorithms in Java" , the chapter "Parsing Arithmetic Expressions". You can start with her. - Pavel Parshin
  • Already advised options. I will add my 5 kopecks: try searching for information on the "method of recursive descent". For example, here is a detailed analysis of the implementation of the method in Java: habrahabr.ru/post/122397 - Alexey
  • The book "Complete Handbook of C #", Herbert Shildt. Chapter 26, "Recursive Descent Syntax Analysis". The book is old, you should not read it entirely, just this chapter. - Alexander Petrov

2 answers 2

If this task causes you to misunderstand, I do not advise you to read about complex but effective methods of syntactic analysis. The elephant must be eaten in parts.

Part 1. Expression parsing. As advised by @Mike, read about the reverse Polish entry and the calculation algorithm using it. It is not difficult at all, intuitively clear and based on simple basic principles. Write a calculator that the expression will actually calculate.

Part 2. Translation. With the successful solution of the previous problem, this is, in fact, simply a creative rethinking of the computational process. The only conditionally difficult exercise here is to figure out how the commands in Polish notation are written in the form of assembly instructions — you just need to do it carefully, the work is purely editorial.

And yes, do not forget about unit tests from the very beginning. And it will be easier to debug, and there will be fewer errors, and it will come in handy in a future career :)

  • But why is everyone so fond of her? - Qwertiy ♦
  1. We build an ordinary parsing tree.
  2. We go around it dfs'om and calculate.
  3. You can see that the transitions between each other in a pair of +- can be done without saving the left argument in the register. Similarly with a pair */ .
    In other cases, the value of the left operand should be placed in the register.

Actually, that's all. But there is one moment. The number of registers is limited, so if the expression is too complex, it is unclear what to do with it.