Question

Write an algorithm that uses a stack, reads from a stream of objects (operations and values) in prefix order, and prints the result of that evaluation.

Trace 2 examples to demonstrate that your algorithm is valid.

Analyze your algorithm with respect to n (the number of objects in the stream)

Answer 1

• Below is th detailed explanation of the the working of algorithm to evaluate a prefix expression using stack.
• Evaluating prefix expression using stack.
• Algorithm:

Evaluate(expression_string):

1. Start a pointer from end of expression_string and start traversing the expression_string till start of the string.

2. If pointer points to character which is operand then push it into stack.

3. If pointer points to character which is operator then pop out two elements from stack and apply the operator on the two operands popped out and push the value which comes back to the stack.

4. Now move backwards i.e, decrement the pointer which points to current character , now points to previous character and repeat from step 2.

5. At the end i.e, after traversing through all characters and evaluating and performing operations we have the answer of the prefix expression on the top of the stack so print it.

• Example 1: +3*52

So pointer currently points to end of the string i.e, to character '2', so following the algorithm if current character is a operand then push it into stack.

stack: [2]

Now decrease pointer by 1 to as we move backwards in the expression string, so pointer now points to '5' , adding it to stack again as it is a operand.

stack: [2 5]

Now pointer points to '*' which is an operator so following step 3 of algorithm we pop two elements from stack and perform this operation using this operator so value comes = 5 * 2= 10, and pushing it back to stack.

stack: [10]

Now pointer points to '3' (after decreasing it by 1) so following step 2 push it into stack.

stack: [10 3]

Now pointer points to '+' so following step 3 pop out two elements from stack and apply operation i.e, 3 + 10 =13 and push it back to stack.

stack: [13]

Now as we traversed the while string , following step 5 we get our answer in the top of the tack i.e, 13.

• Example 2: -3*2+61

So pointer currently points(step 1) to end of the string i.e, to character '1', so following the algorithm if current character is a operand then push it into stack(step 2).

stack: [1]

Now decrease pointer by 1(step 4) to as we move backwards in the expression string, so pointer now points to '6' , adding it to stack again as it is a operand.

stack: [1 6]

Now pointer points to '+' which is an operator so following step 3 of algorithm we pop two elements from stack and perform this operation using this operator so value comes = 6 + 1= 7, and pushing it back to stack.

stack: [7]

Now pointer points to '2' (after decreasing it by 1) so following step 2 push it into stack.

stack: [7 2]

Now pointer points to '*' so following step 3 pop out two elements from stack and apply operation i.e, 2 * 7 =14 and push it back to stack.

stack: [14]

Now pointer points to '3' (after decreasing it by 1) so following step 2 push it into stack.

stack: [14 3]

Now pointer points to '-' so following step 3 pop out two elements from stack and apply operation i.e, 3 - 14 =-11 and push it back to stack.

stack: [-11]

Now as we traversed the while string , following step 5 we get our answer in the top of the tack i.e, -11.

• Time complexity analysis:

So as we can see form the above algorithm and examples we just use one traversal of the string to get our evaluated answer where in each iteration we either add the operand directly to stack or we perform operation after popping two elements from stack and then add it back to stack, so these are constant time operation i.e O(1) as accessing stack top element is done in O(1) time so overall we get n+some constant time operation where n is number if objects in stream(or the length of the expression string).

So time complexity comes out to be O(n) i.e, linear.

So if you still have any doubt regarding this solution please feel free to ask it in the comment section below and if it is helpful then please upvote this solution, THANK YOU.