表达式

时间限制:2s      空间限制:128MB

题目描述

Tar的第一项家庭作业是一大堆中缀表达式。他要把这些表达式写成后缀形式之后交给老师。Tar不会做这个作业,所以他找同学要了一份答案来抄。Tar的老师是一个近视眼,分不清连续一串的相同字符和一个字符的区别。Tar今天感觉非常累,于是他决定偷懒,少抄几个字糊弄一下老师。请你帮他完成这个任务。
我们来做几个必要的定义。
表达式由a-z的小写字母和一些二元运算符构成,运算符可以是a-z以外的任意可见字符。
中缀表达式就是一般情况下使用的表达式,比如((a+h)/b)*(c+d),将运算符置于两个运算数中间(注意运算数本身可以是变量或者一个表达式,因此这是一个递归定义)。一般可以利用括号指定运算顺序。
后缀表达式的特点是把运算符置于两个运算数之后,比如和上式等价的后缀表达式是ah+b/cd+*。后缀表达式不需要括号,严格从左到右进行计算。
另外我们假定这个表达式系统内,相同的运算符号满足结合律和交换律,具体来说:
结合律:A*(B*C) = (A*B)*C 写成后缀时,ABC** = AB*C*。
交换律:A*B = B*A 写成后缀时,AB* = BA*


输入格式

一行字符,表示Tar同学的答案。以后缀表达式的形式给出。


输出格式

输出一个数字,表示Tar能够蒙混过关至少要写几个字。


样例输入

样例输入1
af+b*cd**

样例输入2
xy*x*y*x*y*

样例输出

样例输出1
7

样例输出2
3

提示

样例解释2
xy*x*y*x*y* = xxxyyy***** = (xy*) 长度为3
100%的数据满足:输入长度<=2500


题目来源

没有写明来源

Menuappsclose