Write a C++ program that will accept infix expressions (like 5*(4+8)) and

convert them to postfix. You are to use Dijkstra's algorithm for converting.

The stack routines are to be defined as methods in a class and are to be in a separate file.

Dijkstra's Algorithm:

Read in 1 line into a string

Print the string

while there are characters left to process in the string

-----

| get a token (skip over blanks)

| if the token is a digit then output(token)

| else

| -----

| | if the token is '(' then push(token)

| | else

| | -----

| | | if the token is ')' then

| | | -----

| | | | while the top item is not '('

| | | | pop(temp) and output(temp);

| | | | pop(temp)

| | | -----

| | | else

| | | -----

| | | | if the stack is empty then push(token)

| | | | else

| | | | -----

| | | | | while the stack is not empty

| | | | | and the priority (token) <= priority (top item on the stack)

| | | | | pop(temp) and output(temp)

| | | | | push(token)

| | | | -----

| | | -----

| | ----

| -----

-----

while the stack is not empty do pop(temp) and output(temp)

Precedence of the Operators:

operators : ^ * / + - (

precedence: 3 2 2 1 1 0

where ^ means exponentiation

input for the assignment:

2 + 3 * 5

2 + 3 * 5 ^ 6

2 + 3 - 5 + 6 - 4 + 2 - 1

2 + 3 * (5 - 6) - 4

2 * 3 ^ 5 * 6 - 4

(2 + 3) * 6 ^ 2

Output for the assignment

1: 2 + 3 * 5

235*+

2: 2 + 3 * 5 ^ 6

2356^*+

3: 2 + 3 - 5 + 6 - 4 + 2 - 1

23+5-6+4-2+1-

4: 2 + 3 * (5 - 6) - 4

2356-*+4-

5: 2 * 3 ^ 5 * 6 - 4

235^*6*4-

6: (2 + 3) * 6 ^ 2

23+62^*

Write a C++ program that will accept infix expressions (like 5*(4+8)) and

convert them to postfix. You are to use Dijkstra's algorithm for converting.

The stack routines are to be defined as methods in a class and are to be in a separate file.

Dijkstra's Algorithm:

Read in 1 line into a string

Print the string

while there are characters left to process in the string

-----

| get a token (skip over blanks)

| if the token is a digit then output(token)

| else

| -----

| | if the token is '(' then push(token)

| | else

| | -----

| | | if the token is ')' then

| | | -----

| | | | while the top item is not '('

| | | | pop(temp) and output(temp);

| | | | pop(temp)

| | | -----

| | | else

| | | -----

| | | | if the stack is empty then push(token)

| | | | else

| | | | -----

| | | | | while the stack is not empty

| | | | | and the priority (token) <= priority (top item on the stack)

| | | | | pop(temp) and output(temp)

| | | | | push(token)

| | | | -----

| | | -----

| | ----

| -----

-----

while the stack is not empty do pop(temp) and output(temp)

Precedence of the Operators:

operators : ^ * / + - (

precedence: 3 2 2 1 1 0

where ^ means exponentiation

input for the assignment:

2 + 3 * 5

2 + 3 * 5 ^ 6

2 + 3 - 5 + 6 - 4 + 2 - 1

2 + 3 * (5 - 6) - 4

2 * 3 ^ 5 * 6 - 4

(2 + 3) * 6 ^ 2

Output for the assignment

1: 2 + 3 * 5

235*+

2: 2 + 3 * 5 ^ 6

2356^*+

3: 2 + 3 - 5 + 6 - 4 + 2 - 1

23+5-6+4-2+1-

4: 2 + 3 * (5 - 6) - 4

2356-*+4-

5: 2 * 3 ^ 5 * 6 - 4

235^*6*4-

6: (2 + 3) * 6 ^ 2

23+62^*

Programming Notes:

The stack routines are to be defined as methods in a class and are to be in a separate file.