Software Engineer

You are given a string 'exp' which is a valid infix expression.

Convert the given infix expression to postfix expression.

Note:

Infix notation is a method of writing mathematical expressions in which operators are placed between operands. 

For example, "3 + 4" represents the addition of 3 and 4.

Postfix notation is a method of writing mathematical expressions in which operators are placed after the operands. 

For example, "3 4 +" represents the addition of 3 and 4.

Expression contains digits, lower case English letters, ‘(’, ‘)’, ‘+’, ‘-’, ‘*’, ‘/’, ‘^’. 

Example:

Input: exp = ‘3+4*8’

Output: 348*+

Explanation:
Here multiplication is performed first and then the addition operation. Hence postfix expression is  3 4 8 * +.

Given a string ‘strNum’ which represents a number, your task is to find the ways to decode the given string ‘strNum’.

The format of encoding is as follows: ‘A’ - 1, ‘B’ - 2, ‘C’ - 3, ‘D’ - 4, ……………, ‘Z’ - 26.

Encoding is possible in letters from ‘A’ to ‘Z’. There is an encoding between character and number.

Example :

‘n = 226’ so we can decode ‘226’ in such a way-

‘BZ = 2-26’, as B maps to 2 and Z maps to 26.

‘BBF = 2-2-6’

‘VF = 22-6’

‘226; can be decoded in three ‘BZ’, ‘BBF’, ‘VF’ possible ways.

Point to be noticed we can’t decode ‘226’ as ‘226’ because we have no character which can directly map with ‘226’ we can only decode numbers from ‘1’ to ‘26’ only.

You are given a Trie data structure which stores words or strings and a string 'WORD'. Your task is to perform the delete operation on the Trie to delete an input string 'WORD' from it.

You have to complete the function deleteWord() which takes the root of input Trie 'ROOT' and a string 'WORD' as parameters and returns a TrieNode pointer. If the string 'WORD' exists in the trie, it must be deleted, and the root of new Trie should be returned. If the correct word is deleted, the output will be “TRUE” else it will be “FALSE”.

If the string “word” doesn’t exist in the Trie, then no delete operation will take place, and the output will be “TRUE”. If for any query, the output is “FALSE”, then the answer is wrong.

Trie is a data structure which is like a tree data structure in its organization. It consists of nodes that store letters or alphabets of words, which can be added, retrieved, and deleted from the trie in a very efficient way. In other words, Trie is an information retrieval data structure, which can beat naive data structures like Hashmaps, Trees etc. in time complexities of its operations.

Above figure is the representation of a Trie. New words that are added are inserted as the children of the root node. Alphabets are added in the top to bottom fashion in parent to children hierarchy. Alphabets that are highlighted with blue circles are the end nodes which mark the ending of a word in the Trie.

To define this problem, we perform operations with the following two types of queries.

To insert a string WORD in the Trie, we use ‘’Type 1’’ query.

Example: 1 WORD 

We will put the integer 1 before the input string WORD to insert it into the Trie.

To delete the string  WORD from the Trie, we use the “Type 2” query.

Example: 2 WORD

We will put integer 2 before the input string WORD to delete the string WORD from the Trie.

Example:-

Query A - 1 coding
This query will add the string “coding” in the trie.

Query B - 2 coding
This query will delete the string “coding” from the Trie. After deleting the string, it will produce “TRUE” as it’s output.

Note:

If anywhere in the output, the word “FALSE” is printed, it means that the given string is not deleted successfully from the Trie, and hence it will lead to a Wrong Answer.