Show problems as
Classic problem #2232MediumStringEnumeration

Minimize Result by Adding Parentheses to Expression

Real-world version: Bracketing A Two-Run Price Ticket
Tracked in this browser only
Read Minimize Result by Adding Parentheses to Expression on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A market stall writes its prices as a ticket: a run of digits, a single '+', then another run of digits. Every digit is between '1' and '9', and both runs hold at least one digit.

The stallholder must add one '(' and one ')' to the ticket. The '(' goes immediately before one of the digits of the left run, and the ')' goes immediately after one of the digits of the right run, so the '+' always ends up inside the brackets. Nothing else about the ticket may change.

The bracketed ticket is then read like this: the bracketed part is the sum of the two digit runs inside it, and any digits left outside the brackets, on either side, multiply that sum. So 2(7+3)45 reads as 2 times 10 times 45. A side with no digits left outside contributes no multiplier at all.

Return the bracketed ticket, as a string, whose reading is the smallest possible. If several placements tie for the smallest reading, return the one whose '(' sits furthest left, and among those the one whose ')' sits furthest left.

Work the value out yourself: do not hand the ticket to a built-in expression evaluator.

Examples

Example 1

Input
ticket = "84+27"
Output
"(84+27)"

The whole ticket finishes up inside the brackets, so the reading is 84 plus 27, which is 111.

Example 2

Input
ticket = "7+652"
Output
"(7+65)2"

With the 2 left outside on the right, the ticket reads 72 times 2, which is 144.

Example 3

Input
ticket = "5391+8"
Output
"5(391+8)"

With the 5 left outside on the left, the ticket reads 5 times 399, which is 1995.

Constraints

  • 3 <= ticket.length <= 10
  • ticket consists of the digits '1' to '9' and the character '+'.
  • ticket starts and ends with a digit.
  • ticket contains exactly one '+'.
  • The reading of the ticket, and of the ticket after any legal placement of the brackets, fits in a signed 32-bit integer.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def bracket_ticket(ticket: str) -> str:
Java
public String bracketTicket(String ticket)

More on the same topics