当前你的浏览器版本过低,网站已在兼容模式下运行,兼容模式仅提供最小功能支持,网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。

建议使用的浏览器:

谷歌Chrome 火狐Firefox Opera浏览器 微软Edge浏览器 QQ浏览器 360浏览器 傲游浏览器

3203:Incremental Python Parsing

题目描述

For the sake of simplicity, only the following subset of Python syntax is considered:

PLAIN_TEXT:
    [^"()\[\]{}]+

STRING:
    \"[^"]*\"

text:
      (empty)
    |
text PLAIN_TEXT
    |
text STRING
    |
text bracket_enclosed_text
bracket_enclosed_text:
      ( text )
    | [ text ]
    | { text }

From the syntax some terms are defined as follows:

  1. String: a sequence delimited by quotes (") of characters other than quotes, possibly including new-lines.

    Examples:
      "a(bc"
      "a
    bc)"
      "usage: foo [bar]
    this help information
    is
    totally
    useless"

    (Python actually """ for such strings, but let’s accept the modification just for this problem.)

  2. Bracket-enclosed text: a sequence of characters other than brackets or quotes enclosed by matched pairs of brackets.

    Example:
      (1)
      {a->[foo.bar(
      "a[",b,c
      )]}

  3. Logical new-line: a new-line character that is not part of a string or bracket-enclosed text

  4. Physical line: a maximal sequence of characters other than new-line characters

    Examples:
    def a(b)    # physical line 1
      foo.bar( 
    # physical line 2
      "a[",b)  
    # physical line 3
    "blah blah,
    # physical line 4
    blah"      
    # physical line 5

  5. Logical line: a maximal sequence of characters other than logical new-lines

    Examples:
    def a(b)    # logical line 1
      foo.bar( 
    # logical line 2
      "a[",b)  
    # logical line 2
    "blah blah,
    # logical line 3
    blah"      
    # logical line 3 

  6. Valid/invalid program: a program without/with mismatched quotes or brackets that are not part of any strings 

    Examples:
      def a(b
      "blah

Given a program, you are to implement the following primitive operations:

  • modify(a, b, c): Modify the character at physical line a, column b to c
  • query(a, b): Tell which logical line the character at physical line a, column b is on.
输入解释

The given program appears first in the input followed by a line with a single #. Then come the operation descriptions. Each operation is described in the format c a b, where c is a character, a a physical line number and b a column number. Both physical line and column numbers are counted starting from 1. If c is ?, the operation will be query(a, b), otherwise it will be modify(a, b, c). The program can be invalid while being edited, but whenever a query operation is demanded, it will always be valid. A modify operation will neither remove existing spaces and new-lines in the program nor introduce new ones. Tabs are not present in the input.

The program contains up to 106 characters (including new-lines) and 105 physical lines each consisting of up to 80 characters. And there will be at most 105 operations.

输出解释

For each query operation, output a line containing the logical line number.

输入样例
aaa
(bb
ccc
dd)
fff
#
? 1 1
? 5 1
b 2 1
d 4 3
? 5 1
" 1 3
" 5 2
? 5 1
a 1 3
f 5 2
? 5 1
输出样例
1
3
5
1
5

该题目是Virtual Judge题目,来自 北京大学POJ

源链接: POJ-3203

最后修改于 2020-10-29T06:55:45+00:00 由爬虫自动更新

共提交 0

通过率 --%
时间上限 内存上限
2000 131072