#6404. 「ICPC World Finals 2018」逗号播撒机

内存限制:1024 MiB 时间限制:8000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

学习英语的人迟早会明白,英语语法中逗号的添加规则相当复杂、麻烦、且存在歧义。包括母语为英语的人在内的大多数人实际上会忽视这些规则并自己想出一套规则,甚至没有任何规则。

逗号播撒机老师制定了一套无歧义、不简单的规则,从而解决了这个问题。在本题中,你将会帮助播撒机老师编写算法来自动按照他的规则添加逗号。

播撒机老师对已有的文字添加逗号的规则如下:

  1. 如果在文本的任何位置有一个词语的前面有一个逗号,就在文本中找到该词语出现的所有位置,并在该词语前面添加一个逗号,除非该词语是该句子的第一个词语,或者词语前面已经有一个逗号。

  2. 如果在文本的任何位置有一个词语的后面有一个逗号,就在文本中找到该词语出现的所有位置,并在该词语后面添加一个逗号,除非该词语是该句子的最后一个词语,或者词语后面已经有一个逗号。

  3. 重复 1 和 2 直到无法再添加新的逗号。

举例来说,考虑这样一段文字

please sit spot. sit spot, sit. spot here now here.

因为第二句在 spot 的后面有一个逗号,所以在第三句的 spot 后面也应该添加一个逗号(但第一个句子不用,因为第一句中 spot 是最后一个词语)。同时,由于在第二句中第二个 sit 前面有一个逗号,所以在第一句的 sit 前面也要添加一个逗号(第二个句子的第一个 sit 是第二句的第一个词语,所以不用添加逗号)。最后,发现第三句的 here 前面多出了一个逗号,因此在 here 所有出现位置的前面也添加一个逗号。无法再添加更多的逗号,所以最终的结果是

please, sit spot. sit spot, sit. spot, here now, here.

输入格式

输入只有一行文本,字符数量不少于 2 ,不大于 1\ 000\ 000

每个字符可能是以下四项之一:小写字母、逗号、句号或空格。定义单词为文本中的极长连续字母串。该文本满足以下约束条件:

  • 文本开头一定是一个单词。
  • 每两个单词之间要么有一个空格,一个逗号紧接着一个空格,或者一个句号紧接着一个空格(表示一个句子的结束和另一个句子的开始)。
  • 文本结尾一定是一个句号,且没有多余空格。

输出格式

输出文本经过播撒机老师算法处理后得到的结果。

样例

样例输入 1

please sit spot. sit spot, sit. spot here now here.

样例输出 1

please, sit spot. sit spot, sit. spot, here now, here.

样例输入 2

one, two. one tree. four tree. four four. five four. six five.

样例输出 2

one, two. one, tree. four, tree. four, four. five, four. six five.

数据范围与提示

字符串长度不短于 2 个字符,不长于 1\ 000\ 000 个字符。

在不侵犯原题版权的情况下,本题面中文翻译基于知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议发布,注明出处时需指向本题链接。