Problem:


ICPC Calculator

In mathematics, we usually specify the order of operations by using
parentheses.
For example, 7 × (3 + 2) always means multiplying 7 by the result of 3 + 2 and never means adding 2 to the result of 7 × 3.

However, there are people who do not like parentheses.
International Counter of Parentheses Council (ICPC) is attempting
to make a notation without parentheses the world standard.
They are always making studies of such no-parentheses notations.

Dr. Tsukuba, a member of ICPC, invented a new parenthesis-free notation.
In his notation, a single expression is represented by multiple
lines, each of which contains an addition operator (+), a
multiplication operator (*) or an integer.
An expression is either a single integer or an operator application to operands.
Integers are denoted in decimal notation in one line.
An operator application is denoted by a line of its operator immediately
followed by lines denoting its two or more operands,
each of which is an expression, recursively.
Note that when an operand is an operator application,
it comprises multiple lines.

As expressions may be arbitrarily nested,
we have to make it clear which operator is applied to which operands.
For that purpose, each of the expressions is given its nesting level.
The top level expression has the nesting level of 0.
When an expression of level n is an operator application,
its operands are expressions of level n + 1.
The first line of an expression starts with a sequence of periods (.),
the number of which indicates the level of the expression.

For example, 2 + 3 in the regular mathematics is denoted as in Figure 1.
An operator can be applied to two or more operands.
Operators + and * represent operations
of summation of all operands and multiplication of all operands,
respectively.  For example, Figure 2 shows an expression multiplying
2, 3, and 4.
For a more complicated example, an expression (2 + 3 + 4) × 5 in
the regular mathematics can be expressed as in Figure 3 while (2 + 3) × 4 × 5
can be expressed as in Figure 4.

+
.2
.3

Figure 1: 2 + 3

*
.2
.3
.4

Figure 2: An expression multiplying 2, 3, and 4

*
.+
..2
..3
..4
.5

Figure 3: (2 + 3 + 4) × 5

*
.+
..2
..3
.4
.5

Figure 4: (2 + 3) × 4 × 5

  Your job is to write a program that computes the value of expressions
  written in Dr. Tsukuba's notation to help him.

Input

  The input consists of multiple datasets.  Each dataset
  starts with a line containing a positive integer n, followed by
  n lines denoting a single expression in Dr. Tsukuba's notation.

  You may assume that, in the expressions given in the input,
  every integer comprises a single digit and that
  every expression has no more than nine integers.
  You may also assume that all the input expressions are valid
  in the Dr. Tsukuba's notation.
  The input contains no extra characters, such as spaces or empty lines.

  The last dataset is immediately followed by a line with a single zero.

Output

For each dataset, output a single line containing an integer
which is the value of the given expression.

Sample Input

1
9
4
+
.1
.2
.3
9
+
.0
.+
..*
...1
...*
....1
....2
..0
10
+
.+
..6
..2
.+
..1
..*
...7
...6
.3
0

Output for the Sample Input

9
6
2
54



Sample input:
1
9
4
+
.1
.2
.3
9
+
.0
.+
..*
...1
...*
....1
....2
..0
10
+
.+
..6
..2
.+
..1
..*
...7
...6
.3
0


Sample output:
9
6
2
54

Submission status: Accepted

Solution code:
#2005_c
"""
n = int(input())
k = list("mcxi")
for i in range(n):
    d = {"m":0,"c":0,"x":0,"i":0}
    a,b  = input().split()
    a = list(a)
    b = list(b)
    a.insert(0,1)
    b.insert(0,1)
    for j in range(1,len(a)):
        if a[j] in k:
            if a[j-1] in k:
                d[a[j]] += 1
            else:
                d[a[j]] += int(a[j-1])
    for j in range(1,len(b))[::-1]:
        if b[j] in k:
            if b[j-1] in k:
                d[b[j]] += 1
            else:
                d[b[j]] += int(b[j-1])
            if d[b[j]] >= 10:
                l = b[j]
                while d[l] >= 10:
                    d[l] -= 10
                    l = k[k.index(l)-1]
                    d[l] += 1
    for j in k:
        if d[j]:
            if d[j] == 1:
                print(j,end = "")
            else:
                print(str(d[j])+j,end = "")
    print()
"""

#2017_c
"""
while 1:
    h, w = map(int, input().split())
    if h == w == 0:
        break
    s = [list(map(int, input().split())) for i in range(h)]

    ans = 0
    for u in range(h):
        for d in range(u+2,h):
            for l in range(w):
                for r in range(l+2,w):
                    m = float("inf")
                    for i in range(u,d+1):
                        m = min(m,s[i][l],s[i][r])
                    for i in range(l,r+1):
                        m = min(m,s[u][i],s[d][i])
                    f = 1
                    su = 0
                    for i in range(u+1,d):
                        for j in range(l+1,r):
                            su += (m-s[i][j])
                            if s[i][j] >= m:
                                f = 0
                                break
                        if not f:
                            break
                    if f:
                        ans = max(ans,su)
    print(ans)
"""

#2016_c
"""
while 1:
    m,n = map(int, input().split())
    if m == n == 0:
        break
    d = {}
    ma = 7368791
    for i in range(m,ma+1):
        d[i] = 1
    z = m
    for i in range(n):
        for j in range(z,ma+1):
            if d[j]:
                z = j
                break
        j = 1
        while z*j <= ma:
            d[z*j] = 0
            j += 1
    for j in range(z,ma+1):
        if d[j]:
            print(j)
            break
"""

#2018_c
"""
def factorize(n):
    if n < 4:
        return [1,n]
    i = 2
    l = [1]
    while i**2 <= n:
        if n%i == 0:
            l.append(i)
            if n//i != i:
                l.append(n//i)
        i += 1
    l.append(n)
    l.sort()
    return l
while 1:
    b = int(input())
    if b == 0:
        break
    f = factorize(2*b)
    for n in f[::-1]:
        a = 1-n+(2*b)//n
        if a >= 1 and a%2 == 0:
            print(a//2,n)
            break
"""

#2010_c
"""
import sys
dp = [100]*1000000
dp_2 = [100]*1000000
dp[0] = 0
dp_2[0] = 0
for i in range(1,181):
    s = i*(i+1)*(i+2)//6
    for j in range(s,1000000):
        if dp[j-s]+1 < dp[j]:
            dp[j] = dp[j-s]+1
    if s%2:
        for j in range(s,1000000):
            if dp_2[j-s]+1 < dp_2[j]:
                dp_2[j] = dp_2[j-s]+1
while 1:
    m = int(sys.stdin.readline())
    if m == 0:
        break
    print(dp[m],dp_2[m])
"""

#2015_c
from collections import deque
while 1:
    n = int(input())
    if n == 0:
        break
    s = [input() for i in range(n)]
    d = [s[i].count(".") for i in range(n)]
    m = max(d)
    c = [s[i][-1] for i in range(n)]
    q = deque()
    for i in range(1,m+1)[::-1]:
        j = 0
        while j < n:
            for k in range(j,n):
                if d[k] == i:break
            else:
                break
            j = k
            op = c[j-1]
            while j < n and d[j] == i:
                q.append(j)
                j += 1
            j = k
            if op == "+":
                k = 0
                while q:
                    x = q.pop()
                    k += int(c[x])
                    c.pop(x)
                    d.pop(x)
                    n -= 1
            else:
                k = 1
                while q:
                    x = q.pop()
                    k *= int(c[x])
                    c.pop(x)
                    d.pop(x)
                    n -= 1
            c[j-1] = k
    print(c[0])

Submission status: Accepted

Solution code:
import re

while True:
    N = int(input())
    if N == 0:
        break
    formula = [input() for _ in range(N)]
    # print(formula)
    stack = []

    for i in reversed(formula):
        # print(stack)
        if re.match("\.*(\*|\+)", i):
            depth = i.count(".")
            i = i.replace(".", "")
            # print(i, depth)
            if i == "+":
                cal_num = 0
            else:
                cal_num = 1
            for s in reversed(stack):
                if re.match("\." * (depth+1) + "\d", s):
                    num = int(s.replace(".", ""))
                    # print(cal_num)
                    if i == "+":
                        cal_num += num
                    else:
                        cal_num *= num
                    stack.pop()
            stack.append("." * depth + str(cal_num))
        else:
            stack.append(i)
    print(stack[0])

Submission status: Accepted

Solution code:
while True:
  n = int(input())
  if n==0:
    break
  if n==1:
    print(int(input()))
    continue

  op = "+*"
  f = [input() for i in range(n)]
  f = f[::-1]
  stack = []

  for i in range(n):
    if f[i][-1] not in op:
      stack.append(f[i])
    else:
      nest = f[i].count(".")
      if f[i][-1]=="*":
        cur = 1
        while len(stack):
          if stack[-1].count(".")!=nest+1:
            break
          else:
            t = stack.pop().strip(".")
            cur *= int(t)
        stack.append("."*(nest)+str(cur))
      else:
        cur = 0
        while len(stack):
          if stack[-1].count(".")!=nest+1:
            break
          else:
            t = stack.pop().strip(".")
            cur += int(t)
        stack.append("."*(nest)+str(cur))
  print(stack[0])

Submission status: Accepted

Solution code:
for n in iter(input, '0'):
    st = ''
    prv_lv = 0
    ops = ['']
    for _ in range(int(n)):
        line = input()
        lv = line.count('.')
        op = line[lv:]
        while prv_lv > lv:
            ops.pop()
            st += ')'
            prv_lv -= 1
        if op in '*+':
            st += ops[-1]
            st += '(' + str(int(op == '*'))
            ops.append(op)
        else:
            st += ops[-1] + op
        prv_lv = lv
    while len(ops) > 1:
        ops.pop()
        st += ')'
    print(eval(st))

Submission status: Accepted

Solution code:
from functools import reduce
import operator

while True:
  n = int(input())
  if n == 0:break
  def fix(x):
    if x[-1] in ("+", "*"):
      return (x.count("."), x[-1])
    else:
      return (x.count("."), int(x[-1]))

  lst = [fix(input()) for _ in range(n)]
  while True:
    if len(lst) == 1:
      print(lst[0][1])
      break
    
    max_depth = -1
    index = 100
    op = "-"
    for i, t in enumerate(lst):
      d, v = t
      if d > max_depth and v in ("+", "*"):
        max_depth = d
        index = i
        op = v

    pop_lst = []
    acc_lst = []
    i = index + 1
    while i < len(lst) and lst[i][0] == max_depth + 1:
      pop_lst.append(i)
      acc_lst.append(lst[i][1])
      i += 1
    if op == "+":
      new_value = reduce(operator.add, acc_lst)
    else:
      new_value = reduce(operator.mul, acc_lst)

    for i in reversed(pop_lst):
      lst.pop(i)
    lst.pop(index)
    lst.insert(index, (max_depth, new_value))

Submission status: Accepted

Solution code:
import functools
import operator

def calc(exps, level):
    lst = []
    while exps:
        exp = exps[0]
        nlevel = len(exp)-1

        if nlevel < level:
            break
        else:
            val = exps.pop(0)[-1]
            if val in ('+', '*'):
                operand = calc(exps, level+1)
                if val == '+':
                    val = sum(operand)
                else:
                    val = functools.reduce(operator.mul, operand)

            elif '0' <= val <= '9':
                val = int(val)

            lst.insert(0, val)

    return lst

def main():
    while True:
        n = int(input().strip())
        if n == 0:
            break
        exps = [input().strip() for _ in range(n)]
        print(calc(exps, 0)[0])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# coding: utf-8
from functools import reduce
def check(dt,st,lv):
    global p
    if p>=len(dt):
        return st
        
    if not dt[p][-1].isdigit() and lv==len(dt[p]):
        tmp=p
        p+=1
        st.append(reduce(lambda a,b:a+b if dt[tmp][-1]=='+' else a*b,check(dt,[],lv+1)))
        return check(dt,st,lv)

    elif lv==len(dt[p]):
        st.append(int(dt[p][-1]))
        p+=1
        return check(dt,st,lv)
    else:
        return st

    
while 1:
    n=int(input())
    if n==0:
        break
    data=[]
    for i in range(n):
        data.append(list(input()))
    p=0
    print(check(data,[],1)[0])

Submission status: Runtime Error

Solution code:
while True:
    n=int(input())
    if n==0:
        break;
    li=[input() for i in range(n)]
    index=0
    def pls(depth):
        k=0
        global index
        while len(li[index])>depth and li[index][depth-1]=='.':
            if (not li[index][depth]=='+') and (not li[index][depth]=='*'):
                k+=int(li[index][depth])
                if not index==n-1:
                    index+=1
                else:
                    return k
            elif li[index][depth]=='+':
                index+=1
                k+=pls(depth+1)
            elif li[index][depth]=='*':
                index+=1
                k+=prd(depth+1)
        else:
            return k
    def prd(depth):
        k=1
        global index
        while len(li[index])>depth and li[index][depth-1]=='.':
            if (not li[index][depth]=='+') and (not li[index][depth]=='*'):
                k*=int(li[index][depth])
                if not index==n-1:
                    index+=1
                else:
                    return k
            elif li[index][depth]=='+':
                index+=1
                k*=pls(depth+1)
            elif li[index][depth]=='*':
                index+=1
                k*=prd(depth+1)
        else:
            return k
    if li[0]=='+':
        index+=1
        print(pls(1))
    elif li[0]=='*':
        index+=1
        print(prd(1))

Submission status: Runtime Error

Solution code:
while True:
    n = int(input())
    if n == 0:break
    a = [input() for _ in range(n)]
    while True:
        if len(a) == 1:break
        c = 0
        s = 0
        for i in range(len(a)):
            if a[i].count('.') > c:
                c = a[i].count('.')
                s = i
        e = s
        while e < len(a) and a[e].count('.') == a[s].count('.'):
            e += 1
        k = a[s - 1]
        k.remove('.')
        b = [a[i] for i in range(s, e)]
        for i in len(b):
            b[i].remove('.')
            b[i] = int(b[i])
        if k == '+':
            a[s] = '.'*a[s].count('.')+str(sum(b))
            del a[s + 1:e]
        else:
            m = 1
            for i in b:
                m *= i
            a[s] = '.'*a[s].count('.')+str(m)
            del a[s + 1:e]
    print(a[0])

Submission status: Runtime Error

Solution code:
while True:
    n = int(input())
    if n == 0:break
    a = [input() for _ in range(n)]
    while True:
        if len(a) == 1:break
        c = 0
        s = 0
        for i in range(len(a)):
            if a[i].count('.') > c:
                c = a[i].count('.')
                s = i
        e = s
        while e < len(a) and a[e].count('.') == a[s].count('.'):
            e += 1
        k = a[s - 1].replace('.', '')
        b = [a[i] for i in range(s, e)]
        for i in len(b):
            b[i] = int(b[i].replace('.', ''))
        if k == '+':
            a[s] = '.'*a[s].count('.')+str(sum(b))
            del a[s + 1:e]
        else:
            m = 1
            for i in b:
                m *= i
            a[s] = '.'*a[s].count('.')+str(m)
            del a[s + 1:e]
    print(a[0])

Submission status: Runtime Error

Solution code:
while True:
    n = int(input())
    if n == 0:break
    a = [input() for _ in range(n)]
    while True:
        if len(a) == 1:break
        c = 0
        s = 0
        for i in range(len(a)):
            if a[i].count('.') > c:
                c = a[i].count('.')
                s = i
        e = s
        while e < len(a) and a[e].count('.') == a[s].count('.'):
            e += 1
        k = a[s - 1].replace('.', '')
        b = [a[i] for i in range(s, e)]
        for i in range(len(b)):
            b[i] = int(b[i].replace('.', ''))
        if k == '+':
            a[s] = '.'*a[s].count('.')+str(sum(b))
            del a[s + 1:e]
        else:
            m = 1
            for i in b:
                m *= i
            a[s] = '.'*a[s].count('.')+str(m)
            del a[s + 1:e]
    print(a[0])

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python

from collections import deque
import itertools as it
import sys
import math

while True:
    n = input()
    lst = []
    if n == 0:
        break
    if n == 1:
        num = input()
        print num
        continue
    for loop in range(n):
        S = raw_input()
        lst.append((len(S), S[-1]))
    n += 1
    
    c_lst = [0 for i in range(1000)]
    v_lst = [0 for i in range(1000)]

    rank = 1
    for i in range(n):
        r = lst[i][0]
        c = lst[i][1]
        while r < rank:
            if c_lst[rank - 1] == '+':
                v_lst[rank - 1] += v_lst[rank]
            else:
                v_lst[rank - 1] *= v_lst[rank]
            rank -= 1
        if c == '+':
            r += 1
            c_lst[r] = '+'
            v_lst[r] = 0
            rank += 1
            continue
        elif c == '*':
            r += 1
            c_lst[r] = '*'
            v_lst[r] = 1
            rank += 1
            continue
        if c_lst[r] == '+':
            v_lst[r] += int(c)
        else:
            v_lst[r] *= int(c)
    print v_lst[2]