"""任务 4 · 表达式求值：后缀一遍，中缀两栈

课件里两段能直接跑的代码就是这两件事：

    后缀表达式（逆波兰式）  3 4 + 2 * 写成 '34+2*'：读到数字存起来，读到运算符
                            取最近存进去的两个数算一次，再把结果存回去——一个栈就够。
    中缀表达式（日常写法）  '(1+2)*3'：要两个栈，一个存操作数、一个存运算符，
                            遇到运算符先与运算符栈的栈顶比优先级，决定先算还是先入栈；
                            遇到左括号压进运算符栈，遇到右括号就把运算符栈弹到左括号为止。

这一课的两个函数都写成「一个字符一个字符地读」的版本，操作数与中间结果都是整数。
中缀那一版先用 parse(s) 把字符串切成一段一段（数字可能不止一位，所以要先切再算），
再由 value(s) 走两栈流程。

约定（两份都照这个来）：
    运算符只有 + - * / 四种，/ 是整除（写 //）；
    减法与除法按读到它们的**先后**算，也就是左边那个减/除右边那个；
    题面保证不会出现除以 0。

接口：函数名、造数据那几行、带 print 的行都是判分接口，别改；
要写的是标着 TODO 的两段（中缀那一段分成两小步）。

跑： py task4_eval.py
判： py run_tests.py
"""

from tools import show_count


# ══ TODO 1 ═════════════════════════════════════════════════
# 写 eval_rpn(s)：后缀表达式的求值，s 里每个操作数都是一位数字。
#
# 要点：
#   st = []                          一个栈，存还没参与运算的数
#   读每个字符 ch：
#       ch 是数字（'0123456789' 之一）-> st.append(int(ch))
#       否则（是运算符）              -> b = st.pop()     先弹出的是**右**操作数
#                                       a = st.pop()     后弹出的是**左**操作数
#                                       按 ch 算 a 与 b，结果再 append 回去
#   循环结束时栈里正好剩一个数，它就是答案（return st[-1]）。
#
# 弹出顺序不能写反：栈顶是**后**读到的那个数，也就是右操作数。
# 写反了 '52-' 会从 3 变成 -3、'93/' 会从 3 变成 0——这两组判分都在看。
def eval_rpn(s):
    return 0


# ══ TODO 2 ═════════════════════════════════════════════════
# 中缀表达式求值，分两小步写。
#
# TODO 2a · parse(s)：把字符串切成一段一段，交回一个列表。
#   每一个数字是**一个**元素（收成 int，可能不止一位，所以不能一个字符一个字符地收），
#   每一个运算符是**一个**元素（字符串）。例如 '(12+3)*4' 切出来是
#   ['(', 12, '+', 3, ')', '*', 4]——注意逗号后面那些数字是**没有引号**的。
#
#   要点：扫一遍 s；读到数字就把连续的数字攒成一个整数字符串，遇到别的字符先把这个数
#   收进结果；运算符与括号各自收一个。想法是「用一个临时字符串 num 攒数字」：
#       num = ''
#       读到数字   -> num = num + ch
#       读到别的    -> 如果 num 不是空的，把 int(num) 收进结果、再把 num 清空；
#                      然后把这个字符本身收进结果
#   扫完之后别忘了：num 里可能还留着一个数没收（表达式以数字结尾时就是这种）。
def parse(s):
    return []


# TODO 2b · value(s)：中缀表达式求值，两个栈 + 一张优先级表。
#   优先级表（数字越大越先算，给好的，别改）：{'*': 2, '/': 2, '+': 1, '-': 1}
#
#   流程：
#       nums = []（操作数栈）  ops = []（运算符栈）
#       从头走 parse(s) 切出来的每一段 t：
#         · t 是数字        -> 压进 nums（parse 交回的数字已经是 int，直接 append(t) 即可；
#                              想确认类型可以写 isinstance(t, int)，别对 int 调 .isdigit()）
#         · t 是 '('        -> 压进 ops
#         · t 是 ')'        -> 只要 ops 的栈顶不是 '('，就弹出栈顶运算符算一次
#                              （apply_top 已经给好了：它从两个栈各取一次，算完把结果压回 nums）
#                              最后把栈顶那个 '(' 弹掉、不要它
#         · t 是四种运算符之一 -> 只要 ops 不空、且栈顶不是 '('、
#                              且 PRIORITY[栈顶] >= PRIORITY[t]，就先算栈顶那个
#                              比完再把 t 压进 ops
#       （为什么是「>= 而不是 >」：同优先级的运算符要从左往右算，
#         '9-3+2' 该是 (9-3)+2 = 8，写成 > 会算成 9-(3+2) = 4。）
#       走完之后：只要 ops 不空就一个个算掉，最后 nums 里剩下一个数，就是答案。
def value(s):
    PRIORITY = {'*': 2, '/': 2, '+': 1, '-': 1}     # 别改：优先级表
    nums = []                                      # 别改
    ops = []                                       # 别改

    def apply_top():
        """弹出 ops 的栈顶运算符算一次：取它左右两个操作数，结果压回 nums。"""
        op = ops.pop()
        b = nums.pop()
        a = nums.pop()
        if op == '+':
            nums.append(a + b)
        elif op == '-':
            nums.append(a - b)
        elif op == '*':
            nums.append(a * b)
        else:
            nums.append(a // b)

    # TODO 2b：上面那个流程写在这里
    return 0


if __name__ == '__main__':                     # 别改：这层守卫让判分 import 它时不出声
    rpn_cases = ['34+2*', '12+', '93/', '56+7*', '52-3+']                    # 别改
    rpn_want = [14, 3, 3, 77, 6]                                            # 别改

    for s in rpn_cases:                        # 别改
        print('后缀', s, eval_rpn(s))                                    # 别改

    rpn_ok = True                              # 别改
    for i in range(len(rpn_cases)):            # 别改
        if eval_rpn(rpn_cases[i]) != rpn_want[i]:
            rpn_ok = False
    print('后缀 五组全部对上', rpn_ok)                                    # 别改：期望 True
    print('后缀 减法与除法没有写反', eval_rpn('52-') == 3 and eval_rpn('93/') == 3)   # 别改：期望 True

    print('切分 (12+3)*4', parse('(12+3)*4'))                          # 别改：期望 ['(', 12, '+', 3, ')', '*', 4]
    print('切分 7', parse('7'))                                        # 别改：期望 [7]

    mid_cases = ['12+3', '(1+2)*3', '12*3+4', '9-3+2', '9-3-2', '4*5-6/3']   # 别改
    mid_want = [15, 9, 40, 8, 4, 18]                                        # 别改

    for s in mid_cases:                        # 别改
        print('中缀', s, value(s))                                      # 别改

    mid_ok = True                              # 别改
    for i in range(len(mid_cases)):            # 别改
        if value(mid_cases[i]) != mid_want[i]:
            mid_ok = False
    print('中缀 六组全部对上', mid_ok)                                    # 别改：期望 True
    print('中缀 同优先级从左往右', value('9-3+2') == 8 and value('9-3-2') == 4)       # 别改：期望 True

    show_count(1, '后缀 全部对上', rpn_ok)                                # 别改
    show_count(2, '中缀 全部对上', mid_ok)                                # 别改
    show_count(3, '两种都算对', rpn_ok and mid_ok)                        # 别改