Algorithms and Data Structures
Excercise 3
Stacks and Queues

In this exercise, we will learn about the basic operations with the stacks (Algorithms in C, p.29) and we will write a program. Although queues (Algorithms in C, p.34) are not practiced in this exercise, it is not so difficult to make a queue if you can make a stack.

Question 1PostScript for printing

(1) Write following formulas by RPN (Reverse Poland Notation).

  1. 1 + 2 * 3
  2. ( 1 + 2 ) * 3
  3. ( 1 + 2 ) * ( 3 + 4 )
  4. 1 + ( 2 + 3 ) * 4 + 5

(2) Calculate RPN expression of (1).4 by using stack. And also, write the state of the stack at all stages of the calculation process.

スタックの使用例
Question 2

Write the program which calculates the formula expressed with RPN using a stack. Moreover, fulfill the following conditions.

Execusion Example:
% ./a.out
Input data by Reverse Polish Notation: 12+34+*
1 
1 2 
3 
3 3 
3 3 4 
3 7 
21 
Answer: 21

Try to display this better if you can.

スタックを配列で表現
Question 3

Write the program which calculates the formula expressed with RPN using a stack. However, now you must use a list for making a stack. Other conditions are the same as in problem 2. Moreover, you can use functions which is used in Exercise 2.

Execusion Example:
% ./a.out
Input data by Reverse Polish Notation: 12+34+*
1 
2 1 
3 
3 3 
4 3 3 
7 3 
21 
Answer: 21
スタックを連結リストで表現
連結リストでプッシュ
連結リストでポップ

The original Japanese document was written by Naoki Wakamatsu
This translation document was written by Kenichi Maezu <m5061121@u-aizu.ac.jp>
and Hajime Matsui <m5061122@u-aizu.ac.jp> and checked by L. Pichl.