Problem Statement
Prefix notation (also known as Polish notation in reference to the nationality of its inventor, Jan Lukasiewicz) is a notation where operators are placed before their arguments (and arguments themselves are also expressions in prefix notation). Since the arity of arithmetic operations is fixed, an expression written in prefix notation is always unambiguous, and parenthesizing the expression is unnecessary. For example:
Our usual (infix) notation Prefix notation 2 + 3 + 2 3 3 + 2 + 3 2 4 * (-2 + 3) * 4 + -2 3 (22 + 3) * (55 - 4) * + 22 3 - 55 4 1 + 2 + 3 + 44 + (-5) + + + + 1 2 3 44 -5 1 + (2 + (3 + (44 + (-5)))) + 1 + 2 + 3 + 44 -5
As you can see from the table, any arithmetic expression can be written unambiguously in prefix notation. Since operators and numbers are separated by spaces, we are always able to distinguish a 2-digit number and a sequence of two 1-digit numbers, as well as distinguish between unary and binary minuses.
More formally, any valid expression in prefix notation can be described by the following rules:
- Any integer number is a valid expression.
- If S and Q are valid expressions, then "+ S Q", "* S Q", "- S Q" and "/ S Q" are valid expressions (all quotes are for clarity only).
You've got an expression written in prefix notation and you'd like to read it. Unfortunately, all the spaces were removed, possibly making it impossible to determine what the original expression was. For example, "--456" could have originally been "- - 4 5 6", "- -4 56" or "- -45 6". You are to return the number of different valid original prefix notation expressions that could have resulted in the given expression. Note that both positive and negative numbers in the original expression may contain leading zeroes. Unary minuses in the original expression are allowed, but there can be at most one unary minus in a number (so, "12" and "-34" are valid numbers, but "--11" and "----22" are not). Also, the original expression cannot contain any unary pluses. See examples for further clarification.
Definition
- Class:
- PolishNotation
- Method:
- waysToDecode
- Parameters:
- String
- Returns:
- long
- Method signature:
- long waysToDecode(String expression)
- (be sure your method is public)
Constraints
- expression will contain between 1 and 50 characters, inclusive.
- expression will contain only '+', '-', '/', '*' characters and digits ('0' - '9').
Examples
"01234567890123456789"
Returns: 1
This string is already a valid expression in prefix notation, and the only way to keep it valid is to not add any spaces.
"+1234567"
Returns: 6
We must put a space after '+' to split the operator and its operands. We need one more space to split the two operands, and it can be put right after '1', '2', '3', '4', '5' or '6'.
"23/33"
Returns: 0
This string can not be transformed into a valid expression.
"/-010"
Returns: 3
The three ways to transform this into a valid expression are (all quotes for clarity): "/ -0 10" (the minus is unary) "/ -01 0" (the minus is unary) "/ - 0 1 0" (the minus is binary)
"+++++12345"
Returns: 0
"+++++123456"
Returns: 1
"-*123"
Returns: 1
Here the minus is followed by another operation, so it must be binary.
"-123"
Returns: 3
"-+00000000"
Returns: 21
"---2222222222"
Returns: 120
"++++++++++1111111111111111111111111111111111111111"
Returns: 635745396
"++++++++++11111111111111111111111111"
Returns: 3268760
"++++++++++++++11111112112311111111111111"
Returns: 4457400
"--------------111111111111111111111111111111111111"
Returns: 3796297200
The worst "obvious" case; there may be worse but this is the best I could do.
"--1"
Returns: 0
"+23423+3+3443+2+43+343+24+3432434"
Returns: 6
"-0"
Returns: 1
"-+90-451-*-26-900-+8+75*0-+90/*+/9*9*/73904427"
Returns: 2079
"-9*65-9-/1//-46*63-*9334-1-2575+3+1*51355/54/"
Returns: 0
"-9*65-9-/1//-46*63-*9334-1-2575+3+1*51355/54"
Returns: 1365
"+-/-8323*/4+5+/4/85+92+3684/9/-607"
Returns: 488
"*4051---4+0+87--+3**31928+86"
Returns: 6
"*497*16+82-*3//16*9-318-9+-912//7754044865*9-979"
Returns: 8806
"-1*-3-633*7/876+2603677-*/-594447781578--8687"
Returns: 23068
"//585*/162625+5079*2*--5052679877775/-9-769"
Returns: 48846
"-----------111111111111111111111111111111111111111"
Returns: 1676056044
"------------11111111111111111111111111111111111111"
Returns: 2707475148
"-------------1111111111111111111111111111111111111"
Returns: 3562467300
"--------------111111111111111111111111111111111111"
Returns: 3796297200
"---------------11111111111111111111111111111111111"
Returns: 3247943160
"-66223038--725-*2*35*8/2862/797753159/203"
Returns: 219
"+814869/836426-572423*12"
Returns: 1
"-7-724-4"
Returns: 1
"/7/271512-738547-38878-2500"
Returns: 4
"-6-827925-5-2405-8251-6128-926--*1425-449+0770"
Returns: 64
"+3023-093+4+72--7"
Returns: 0
"-236567688-6677845483"
Returns: 10
"--*-01701158-+4*4813"
Returns: 196
"*+65+070-570-29150"
Returns: 40
"/11*683-9-1"
Returns: 1
"-8029205102+73454397346/794-5537/74378-0/033/78*7"
Returns: 0
"/380/-091-6023/30//278/529003861+291501+-3-825/8"
Returns: 0
"+5723790026-726086443"
Returns: 9
"/88*/484001250-43462/-1601053*4/"
Returns: 0
"-5-+++9896/45918-562347811457201302-1156+-4-32"
Returns: 11368
"+-+50/06866489*42-3316+2*35*184212*9-7374*05/-58"
Returns: 276
"*006+648364360846*+91482+//39+*60*-781-964+938"
Returns: 966
"24*19477327369*160005*45-0+69/2"
Returns: 0
"+-64684248//495/6094-49854477-28+7731132"
Returns: 1715
"*3-1-98"
Returns: 2
"/53810380092906+-+891017/316-5/+3086301665101220-9"
Returns: 1715
"+*632*15*6/2+08+4-554615/3-5+2670553"
Returns: 81
"9+/522841+18+/1965"
Returns: 0
"/-093968557198-8939"
Returns: 54
"/72353329156620-38022*71806/9-*2/*4--580157*-"
Returns: 0
"-"
Returns: 0
"+"
Returns: 0
"2"
Returns: 1
"9999999999----------++++++++++9999999999"
Returns: 0
"+-321-+-/*--++++++---2318323239-210-38413923132134"
Returns: 47549970
"-*+------*+-*+-02843709124739137490127349173249012"
Returns: 3247943160
"--------0000000000001231+223"
Returns: 30888
"--------------167890123456789012345678901234567890"
Returns: 3796297200