Question

In: Computer Science

Stack Time Limit : 1 sec, Memory Limit : 131072 KB English / Japanese   Reverse Polish...

Stack

Time Limit : 1 sec, Memory Limit : 131072 KB
English / Japanese  

Reverse Polish notation is a notation where every operator follows all of its operands. For example, an expression (1+2)*(5+4) in the conventional Polish notation can be represented as 1 2 + 5 4 + * in the Reverse Polish notation. One of advantages of the Reverse Polish notation is that it is parenthesis-free.

Write a program which reads an expression in the Reverse Polish notation and prints the computational result.

An expression in the Reverse Polish notation is calculated using a stack. To evaluate the expression, the program should read symbols in order. If the symbol is an operand, the corresponding value should be pushed into the stack. On the other hand, if the symbols is an operator, the program should pop two elements from the stack, perform the corresponding operations, then push the result in to the stack. The program should repeat this operations.

Input

An expression is given in a line. Two consequtive symbols (operand or operator) are separated by a space character.

You can assume that +, - and * are given as the operator and an operand is a positive integer less than 106

Output

Print the computational result in a line.

Constraints

2 ≤ the number of operands in the expression ≤ 100
1 ≤ the number of operators in the expression ≤ 99
-1 × 109 ≤ values in the stack ≤ 109

Sample Input 1

1 2 +

Sample Output 1

3

Sample Input 2

1 2 + 3 4 - *

Sample Output 2

-3

USE JAVA

Solutions

Expert Solution

CODE IN JAVA:

Test.java file:

// Java proram to evaluate value of a postfix expression

import java.util.Stack;
import java.util.Scanner;
public class Test
{
   // It is a Method to evaluate value of a postfix expression
   static int postfixEvaluation(String expr)
   {
       //create a stack
       Stack<Integer> stack=new Stack<>();
      
       // Scan all characters one by one
       for(int i=0;i<expr.length();i++)
       {
           char ch=expr.charAt(i);
          
           // If the scanned character is an operand (number here),
           // push it to the stack.
           if(Character.isDigit(ch))
           stack.push(ch - '0');
           else if(ch==' ') {
              
           }
          
           // If the scanned character is an operator, pop two
           // elements from stack apply the operator
           else
           {
               int val1 = stack.pop();
               int val2 = stack.pop();
              
               switch(ch)
               {
                   case '+':
                   stack.push(val2+val1);
                   break;
                  
                   case '-':
                   stack.push(val2- val1);
                   break;
                  
                   case '/':
                   stack.push(val2/val1);
                   break;
                  
                   case '*':
                   stack.push(val2*val1);
                   break;
                   default:
                       break;
           }
           }
       }
       return stack.pop();     
   }
  
  
   public static void main(String[] args)
   {
       Scanner sc = new Scanner(System.in);
       System.out.print("Enter the postfix expression:");
       String expr=sc.nextLine();
       System.out.println("postfix expression is:"+expr);
       System.out.println("postfix evaluation: "+postfixEvaluation(expr));
   }
}

OUTPUT:


Related Solutions

Time limit: 5000ms Memory limit: 256mb Description: Given a series of stack operations, please complete the...
Time limit: 5000ms Memory limit: 256mb Description: Given a series of stack operations, please complete the stack ADT to output for respective operations. -------------------------Copy the following code, complete it and submit------------------------- #include <stdio.h> #include <stdlib.h> typedef enum {push = 1, pop, end} Operation; typedef struct Node * PtrToNode; struct Node {     int element;     PtrToNode next;     PtrToNode prev; }; typedef struct ListRecord * List; struct ListRecord {     PtrToNode head;     PtrToNode tail; }; List Create() {    ...
C Programme Time limit: 5000ms Memory limit: 256mb Description: Given a series of queue operations, please...
C Programme Time limit: 5000ms Memory limit: 256mb Description: Given a series of queue operations, please complete the queue ADT to output for respective operations. -------------------------Copy the following code, complete it and submit------------------------- #include <stdio.h> #include <stdlib.h> #include <string.h> typedef enum {enqueue = 1, dequeue, end, isfull, isempty} Operation; struct Queue { int * arr; int capacity; int front; int rear; }; struct Queue * Create(int capacity) { struct Queue * queue = (struct Queue *)malloc(sizeof(struct Queue)); queue->arr = (int*)malloc(sizeof(int)...
ASSEMBLY LANGUAGE x86: Reverse a string using the Run-time stack and a procedures You may want...
ASSEMBLY LANGUAGE x86: Reverse a string using the Run-time stack and a procedures You may want to use your project 4 as a starting point As in the last project we will get a string from the user put it into a buffer called 'source' (ReadString) Copy this string into a buffer called ‘destination’, in reverse order For this project you will use the run-time stack (push & pop) to reverse the string in ‘source’ You must still use indirect...
C++ Memory Allocation: 1) Write a C++ program that allocates static, stack, & heap memory. Your...
C++ Memory Allocation: 1) Write a C++ program that allocates static, stack, & heap memory. Your program does not need to do anything else.  Indicate via comments where memory for at least one variable in each memory area is allocated. a) Write code that allocates static memory (only include one declaration): b) Write code that allocates stack memory (only include one declaration): c) Write code that allocates heap memory (only include one declaration): 2) Edit the C++ program below to include...
f(x) = sec x - 1 / x^2 to find the limit using rationilization
f(x) = sec x - 1 / x^2 to find the limit using rationilization
1) Consider the following infix expressions. What is the equivalent postfix (reverse Polish notation) expression? 16/(5+3)b)...
1) Consider the following infix expressions. What is the equivalent postfix (reverse Polish notation) expression? 16/(5+3)b) A*B+C*Dc) X × Y + W × Z + V × U 2) Consider the postfix (reverse Polish notation) 10 5 + 6 3 - /. What is the equivalent infix expression?
TRUE Or False. 1.   If fraud is involved, there is no time limit on the assessment...
TRUE Or False. 1.   If fraud is involved, there is no time limit on the assessment of a deficiency by the IRS. ____     2.   A Revenue Ruling is a judicial source of Federal tax law. ____     3.   Bree received a scholarship to be used as follows: tuition $8000; room and board $11,000; and books and laboratory supplies $4,000. Bree is required to include only $12,000 in her gross income. ____     4.   Two-thirds of treble damage payments under the antitrust law...
1.) Define Memory 2.) Define each (Capacity and duration/time):    a. sensory memory    b. short-term...
1.) Define Memory 2.) Define each (Capacity and duration/time):    a. sensory memory    b. short-term memory    c. long-term memory 3.) Describe the process of information going through these three memory stages.
(In Java) Design a stack that supports getMin(), pop() and push() in O(1) time. Must use...
(In Java) Design a stack that supports getMin(), pop() and push() in O(1) time. Must use the iterator and comparator, does not need to be a linked list, although it's what I've tried using. I'm using another tester class to test this class. import java.util.Comparator; import java.util.List; import java.util.LinkedList; import java.util.Iterator; import java.util.Stack; import java.util.ListIterator; public class FMinStack<T> implements MinStack<T> { protected Comparator<? super T> comp; T min; protected List<T> ds; public FMinStack() { this(new DefaultComparator<T>()); } public FMinStack(Comparator<? super...
Run No. Cup Temp. (˚C) Time (sec.) 1 C 10 139 1 RT 22 48 1...
Run No. Cup Temp. (˚C) Time (sec.) 1 C 10 139 1 RT 22 48 1 H 46 21 2 C 6 162 2 RT 22 45 2 H 44 20 3 C 8 149 3 RT 22 48 3 H 42 20 Avg. C 8 150 Avg. RT 22 47 Avg. H 44 20.33 Using graphing software such as Excel®, graph the results of Activity 1. Please see the Introduction to Graphing manual for guidance.              a. What are...
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT