C++ ungetc() 函数

在 C++ 中，ungetc() 函数用于将一个字符推回到输入流中。该函数是标准输入/输出库的一部分，通常与文件输入流（FILE* 流）一起使用。

C++ 中的 ungetc() 函数是标准输入/输出库的一部分，用于将一个字符推回到输入流中。其语法为 int ungetc(int c, FILE* stream);。参数是要推回到文件流中的字符 c 和指向文件流的指针。当您想“取消读取”一个字符，允许它被后续的输入操作再次读取时，此函数非常有用。

ungetc() 的语法如下：

在此，c 是要推回到流中的字符，而 stream 是指向文件流的指针。

ungetc() 函数会将字符 c 推回到与给定文件流关联的输入流中。在使用 ungetc() 推回字符后，该流的下一次输入操作将读取推回的字符，而不是从输入源获取新字符。

程序

输出

Read character: H
Read character: e
Read character: l
Read character: l
Read character: o
Read character: 
Read character: w
Read character: o
Read character: r
Read character: l
Read character: d
End of file reached

解释

• 程序使用 std::ifstream 打开一个名为 "example.txt" 的文件进行读取。检查文件流是否成功打开。
• while 循环使用 inputFile.get(ch) 从文件中读取字符。对于每个读取的字符，都会进行处理并打印。
• 在循环内部，会检查字符是否为数字，使用 isdigit(ch)。如果字符是数字，则使用 unget() 将其推回到流中。
• 在循环处理完字符后，程序会尝试使用 get(ch) 再次读取最后一个字符。这演示了推回到流中的数字会被再次读取。
• 程序将字符和消息打印到控制台，以说明字符流和 ungetc() 的使用。
• 此示例模拟了您可能希望以不同方式处理某些字符并将其他字符推回到流中以供进一步处理的场景。程序从文件中读取字符，识别数字，并将它们推回到流中，在更复杂的上下文中演示了 ungetc() 的实际用途。

复杂度分析

时间复杂度

• 给定代码的时间复杂度主要由文件中的字符数以及循环内执行的操作决定。
• while 循环使用 get(ch) 遍历文件中的每个字符。读取每个字符的时间复杂度为 O(1)。
• 循环内的处理和打印操作是常数时间操作 (O(1))，因为它们涉及简单的赋值和打印语句。
• 检查字符是否为数字 (isdigit(ch)) 和随后的 inputFile.unget() 调用也都是常数时间操作。
• 再次读取最后一个字符的尝试 (get(ch)) 也是常数时间操作。
• 考虑到这些因素，代码的整体时间复杂度为 O(N)，其中 N 是文件中的字符数。

空间复杂度

代码的空间复杂度由变量和文件输入流使用的内存决定。让我们进一步分解：

• 程序使用一个字符变量 ch。变量的空间复杂度是常数 (O(1))。
• std::ifstream 对象 inputFile 代表文件输入流。其空间复杂度通常由底层文件大小决定，但在循环的每次迭代中，一次只读取一个字符，并且流本身不会消耗与文件大小成比例的额外空间。
• 考虑到这些因素，代码的整体空间复杂度为 O(1)，因为它使用的内存量恒定，与文件大小无关。

方法-1：错误处理

在错误处理场景中，ungetc() 函数在 C++ 中用于处理从输入流中读取到的意外字符。基本思想是读取一个字符，执行一些检查，如果字符不满足预期条件（表示错误），则将其推回到流中以进行进一步处理或报告。

以下是 ungetc() 如何用于错误处理的更详细解释：

输出

Read character: H

解释

• 程序打开一个文件用于读取。
• 它使用 fgetc() 从文件中读取一个字符。
• 它检查该字符是否意外或表示错误条件（在此例中，如果它是字符 'X'）。
• 如果遇到意外字符，程序会适当地处理错误（在此例中，打印一条错误消息到 stderr），然后使用 ungetc() 将字符推回到流中。
• 如果字符不是意外的，程序将继续进行常规处理。
• 这种方法通过检测意外输入并提供处理错误的机会，而不会丢失从流中读取的字符，从而实现了优雅的错误处理。使用 ungetc() 推回字符使程序在决定如何处理意外输入方面具有灵活性。

复杂度分析

时间复杂度

• 打开文件的时​​间复杂度通常是常数或非常接近常数时间，因为它涉及操作系统调用以获取文件访问权限。因此，我们可以认为此操作为 O(1)。
• 从文件中读取字符的时​​间复杂度也通常被认为是 O(1)，因为它涉及从内部缓冲区或文件系统中获取下一个字符。
• 检查 ch 是否等于 'X' 的条件语句是 O(1)，因为它只是一个简单的比较。
• fprintf 和 ungetc 操作也通常是 O(1)，涉及简单的操作，不依赖于输入的大小。
• fclose 操作通常被认为是 O(1)，涉及关闭文件句柄。
• 总的来说，所提供代码的时​​间复杂度主要由常数时间操作决定，在大多数实际情况下为 O(1)。

空间复杂度

• 存储文件指针的空间复杂度是常数，或 O(1)，因为它只需要存储文件结构地址的内存。
• 存储字符 ch 的空间复杂度也常数，或 O(1)，因为它是一个单独的变量。
• 与错误处理和 ungetc 相关的空间复杂度也为常数，只涉及几个变量，不依赖于输入大小。
• 关闭文件的空间复杂度为 O(1)，因为它涉及释放与文件句柄关联的资源。
• 总而言之，所提供代码的空间复杂度主要由常数大小的变量和文件相关结构决定，在大多数实际情况下为 O(1)。

方法-2：解析数字

解析数字涉及从字符流中提取数值，例如读取一系列数字以形成整数或浮点数。在此上下文中ungetc() 的使用是一种执行前瞻并处理初始读取的字符不标记数字值开始的情况的方法。

输出

Error opening file: No such file or directory

解释

• 程序以读取模式打开一个名为“txt”的文件。
• 它检查文件是否已成功打开。如果文件打开有问题，则会显示错误消息，程序将以非零状态退出。
• 程序使用 fgetc() 读取文件中的第一个字符。将检查此字符以确定它是否标记数字值的开始。
• 程序使用 isdigit() 检查读取的字符是否为数字。如果字符是数字，则表示它可能是数字值的开始，程序将继续相应地处理它。如果字符不是数字，表示它不是数字值的开始，程序将使用 ungetc() 将字符推回到流中以进行进一步处理。
• 在处理完初始字符后，程序可以根据特定的解析逻辑继续处理其余的数字值。此步骤可能涉及从文件中读取更多字符以完成数字值。
• 最后，程序关闭文件以释放关联的资源。
• 总而言之，该代码片段演示了一种通过检查从文件中读取的初始字符来解析数字的策略。假设该字符未指示数字值的开始。在这种情况下，它会使用 ungetc() 推回到流中，从而允许进一步处理或处理非数字情况。此方法适用于需要根据输入数据上下文进行灵活性的解析逻辑的场景。

复杂度分析

时间复杂度

• 打开文件的时​​间复杂度通常是常数或非常接近常数时间，因为它涉及操作系统调用以获取文件访问权限。因此，我们可以认为此操作为 O(1)。
• 从文件中读取字符的时​​间复杂度通常被认为是 O(1)，因为它涉及从内部缓冲区或文件系统中获取下一个字符。
• 此块内的操作也是常数时间。isdigit() 的检查是 O(1)，ungetc() 通常是 O(1)。
• 在初始检查之后，程序可能涉及基于特定解析逻辑的进一步处理。这部分的时​​间复杂度取决于解析逻辑的细节，可能会有所不同。
• 关闭文件的时​​间复杂度通常被认为是 O(1)，因为它涉及释放与文件句柄关联的资源。
• 总的来说，所提供代码的时​​间复杂度主要由常数时间操作决定。

空间复杂度

• 存储文件指针和字符 ch 的空间复杂度是常数，即 O(1)，因为它们是单个变量。
• 与错误处理和 ungetc 相关的空间复杂度也为常数，只涉及几个变量，不依赖于输入大小。
• 关闭文件的空间复杂度为 O(1)，因为它涉及释放与文件句柄关联的资源。
• 总而言之，所提供代码的空间复杂度主要由常数大小的变量和文件相关结构决定，在大多数实际情况下为 O(1)。

方法-3：分词

分词是将字符序列分解为称为标记的更小单元的过程。标记可以代表编程语言或自然语言中的单个单词、符号或其他有意义的元素。在 C++ 中，可以在分词期间使用 ungetc() 函数来处理不属于当前标记的字符的情况，从而更好地控制解析过程。

让我们详细分解分词过程和 ungetc() 的使用：

输出

Error opening file: No such file or directory

解释

• 提供的 C++ 代码演示了分词过程，即以称为标记的较小单元分解字符序列。主要目标是识别输入流中的有意义元素，例如单词或符号。以下是代码中关键概念和步骤的详细解释：
• 程序开始尝试以读取模式打开名为 "input.txt" 的文件。
• 代码检查文件是否成功打开。如果未成功，则打印错误消息并退出程序。缓冲区 (token) 被初始化以存储当前标记的字符。
• 从该文件中读取第一个字符。程序进入一个循环，该循环遍历文件中的字符。
• 对于每个字符，它检查该字符是否属于当前标记，基于 isalnum() 函数（字母数字检查）。如果字符是字母数字的，则将其添加到当前标记缓冲区。
• 如果字符不是字母数字的，表示标记已完成，则使用 ungetc() 将该字符推回到流中。然后处理完成的标记，并重置标记缓冲区以进行下一次迭代。
• 如果标记缓冲区不为空，则表示标记已完成。程序处理完成的标记，例如打印其内容。
• 标记缓冲区被重置，为下一次迭代做准备。整个文件处理完毕后，程序关闭文件。

总而言之，该代码从文件中读取字符，根据字母数字字符识别标记，并处理每个完成的标记。ungetc() 的使用允许程序处理字符不属于当前标记的情况，从而实现对输入流的受控分词。此方法对于需要灵活、可定制的输入解析的场景很有价值。

复杂度分析

时间复杂度

• 打开文件的时​​间复杂度通常是常数或非常接近常数时间。它涉及操作系统调用以获取文件访问权限。此操作可视为 O(1)。
• 从文件读取字符并在一​​次分词循环中处理它们的时间复杂度取决于输入文件 (n) 的长度。在每次迭代中，字符都会被读取和处理一次。因此，此部分的时​​间复杂度为 O(n)。
• 关闭文件的时​​间复杂度通常被认为是常数，或 O(1)，因为它涉及释放与文件句柄关联的资源。
• 总的来说，此代码的时间复杂度的主要因素是文件读取和分词期间的线性字符处理，导致时间复杂度为 O(n)，其中 n 是输入文件的长度。

空间复杂度

• 空间复杂度主要由标记缓冲区 (token) 和从文件中读取的单个字符所需的空间决定。这些组件的空间复杂度为 O(1)。
• 空间复杂度还受到文件指针 (file)、循环控制变量 (ch, tokenIndex) 和其他常数大小变量等变量的影响。这些贡献了恒定的空间量，产生了 O(1) 的空间复杂度。
• 与错误处理、推回字符以及处理完成的标记相关的空间复杂度只涉及几个变量，并且不依赖于输入大小。它也为 O(1)。
• 总而言之，所提供代码的空间复杂度主要由常数大小的变量和标记缓冲区决定，导致 O(1) 的空间复杂度。代码的整体效率很高，文件读取和分词期间具有线性时间复杂度。

方法-4：回溯

回溯是在解析算法（如递归下降解析）中用于处理解析分支不成功的技术。当解析器遇到意外标记或未能匹配特定语法规则时，它可能需要回溯并探索其他解析路径。C++ 中的 ungetc() 函数可以在此上下文中用于撤销从输入流中读取的字符，从而允许解析器探索其他路径。

输出

Error opening file: No such file or directory

解释

• 提供的 C++ 代码实现了对包含变量（单个字母字符）和括号的简化表达式语言的递归下降解析器。parseExpression 函数尝试解析表达式，利用 parseAtomicExpression 函数处理原子表达式，并在解析错误时使用 ungetc 进行回溯。
• parseAtomicExpression 函数检查当前字符是否为字母字符（变量），并成功解析并打印该变量，或者回溯，打印错误消息，然后返回。
• parseExpression 函数通过递归调用自身来处理括号内的表达式。如果成功，它会期望一个闭括号，如果找不到，则回溯，打印错误，然后返回false。如果当前字符不是开括号，则回溯，尝试解析原子表达式。
• 在 main 函数中，程序打开文件，尝试解析整个表达式，打印成功或失败消息，并关闭文件。样本输入“"(a(b)c)”演示了变量和括号的成功解析，产生了预期的输出。

复杂度分析

时间复杂度

• 打开文件的时​​间复杂度通常是常数或非常接近常数时间，表示为 O(1)。
• 打印语句和错误处理涉及每个字符的常数时间操作，并且总体影响与输入大小线性成正比。在实际操作中，与解析逻辑相比，它们对整体时间复杂度​​的贡献相对较小。
• 总的来说，时间复杂度​​的主要因素是文件读取和解析期间的线性字符处理，导致时间复杂度为 O(n)，其中 n 是输入文件的长度。

空间复杂度

• 空间复杂度由文件指针 (file)、循环控制变量 (ch) 和其他常数大小变量等变量决定。这些组件的空间复杂度为 O(1)。
• parseExpression 中的递归可能导致递归调用堆栈。递归的最大深度受输入表达式中括号嵌套级别的限制。在最坏的情况下，它是 O(n)，其中 n 是输入文件的长度。
• 总而言之，空间复杂度主要由常数大小的变量和递归堆栈的深度决定，在最坏情况下为 O(n)。代码的整体效率是合理的，具有与输入文件长度成正比的线性和空间复杂度。