SDE - 1

You are given a string denoting a valid Postfix expression containing ‘+’, ’-’, ’*’, ‘/’ and lowercase letters.

Convert the given Postfix expression into a Prefix expression.

Note:

Postfix notation is a method of writing mathematical expressions in which operators are placed after the operands. For example, "a b +" represents the addition of a and b.

Prefix notation is a method of writing mathematical expressions in which operators are placed before the operands. For example, "+ a b" represents the addition of a and b.

Expression contains lowercase English letters, ‘+’, ‘-’, ‘*’, and  ‘/’. 

Example:

Input: abc*+

Output: +a*bc

Explanation:
For the given postfix expression, infix expression is a+b*c. And it's corresponding prefix expression is +a*bc.

Ninja likes to travel a lot, but at the same time, he wants to save as much money as possible.

There are ‘N’ Stations connected by ‘M’ Trains. Each train that he boards starts from station ‘A’ and reaches destination station ‘B’ with a ticket price ‘P’.

Your task is to return the cheapest price from the given ‘source’ to ‘destination’ with up to ‘K’ stops. If there is no such route, return ‘-1’.

For example:

Input:
5 6
0 1 10
0 2 10
0 3 40
1 4 10
2 4 20
4 3 5
0 3 40 

There are three ways to reach station ‘3’ from station ‘0’. The first path is 0->1->4->3, which will cost us 10+ 10+ 5= 25 and the second path 0->2->4->3 will cost us, 10+ 20+ 5 = 35, and the third path 0->3 will cost us 40. 

We can’t take the first path since K = 1 and in this path, we are taking 2 stops, at station ‘1’ and station ‘4’. 

Similarly, there are 2 stops in the second path. Hence we’ll finally choose the 3rd path i.e. 0->3, which is colored in blue.

You have been given a network of ‘N’ nodes from 1 to ‘N’ and ‘M’ edges. For each edge, you are given three values (ui, vi, wi) where “ui” and “vi” denote the nodes and “wi” denotes an integer value which represents the time taken by a signal to travel from “ui” to “vi”. Now, you are supposed to find the time which a signal takes to travel from a given node ‘K’ to all nodes. If it is impossible for all nodes to receive the signal then print -1.

Note:

The signal which starts from the source node travels to all nodes simultaneously.

You are given D dice, each having F faces numbered 1 to F, both inclusive. The task is to find the possible number of ways to roll the dice together such that the sum of face-up numbers equal the given target S.

Note :

As the answer can be large, return your answer modulo 10^9  + 7.

Follow Up :

Can you solve this using not more than O(S) extra space?