Time Limit: 2 Seconds Memory Limit: 65536 KB
Do you know reverse Polish notation (RPN)? It is a known notation in the area of mathematics and computer science. It is also known as postfix notation since every operator in an expression follows all of its operands. Bob is a student in Marjar University. He is learning RPN recent days.
To clarify the syntax of RPN for those who haven't learnt it before, we will offer some examples here. For instance, to add 3 and 4, one would write "3 4 +" rather than "3 + 4". If there are multiple operations, the operator is given immediately after its second operand. The arithmetic expression written "3 - 4 + 5" in conventional notation would be written "3 4 - 5 +" in RPN: 4 is first subtracted from 3, and then 5 added to it. Another infix expression "5 + ((1 + 2) × 4) - 3" can be written down like this in RPN: "5 1 2 + 4 × + 3 -". An advantage of RPN is that it obviates the need for parentheses that are required by infix.
In this problem, we will use the asterisk "*" as the only operator and digits from "1" to "9" (without "0") as components of operands.
You are given an expression in reverse Polish notation. Unfortunately, all space characters are missing. That means the expression are concatenated into several long numeric sequence which are separated by asterisks. So you cannot distinguish the numbers from the given string.
You task is to check whether the given string can represent a valid RPN expression. If the given string cannot represent any valid RPN, please find out the minimal number of operations to make it valid. There are two types of operation to adjust the given string:
- Insert. You can insert a non-zero digit or an asterisk anywhere. For example, if you insert a "1" at the beginning of "2*3*4", the string becomes "12*3*4".
- Swap. You can swap any two characters in the string. For example, if you swap the last two characters of "12*3*4", the string becomes "12*34*".
The strings "2*3*4" and "12*3*4" cannot represent any valid RPN, but the string "12*34*" can represent a valid RPN which is "1 2 * 34 *".
Input
There are multiple test cases. The first line of input contains an integer T indicating the number of test cases. For each test case:
There is a non-empty string consists of asterisks and non-zero digits. The length of the string will not exceed 1000.
Output
For each test case, output the minimal number of operations to make the given string able to represent a valid RPN.
Sample Input
3 1*1 11*234** *
Sample Output
1 0 2
题意:
给出 T 组样例,每个样例都有一串数字 + * 的字符串。问最少需要多少个操作使其变为逆波兰式,可以增加字符进去,也可以任意交换两个字符的位置。
思路:
当 num < star + 1 的时候才需要添加数字进去,设添加的数字数为 k ,之后统计的时候,num 数初始值设为 k,star 数初始值设为 0,再从头开始扫一遍,若遇到当前 num < star + 1,说明需要交换操作。最后输出 k + 交换次数 即为答案。
AC:
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; char str[1005]; int main() { int t; scanf("%d", &t); while (t--) { scanf("%s", str); int len = strlen(str); int num = 0, star = 0; for (int i = 0; i < len; ++i) { if (str[i] == '*') ++star; else ++num; } int k = star + 1 - num; if (k < 0) k = 0; int sum = k; num = k; star = 0; for (int i = 0; i < len; ++i) { if (str[i] == '*') ++star; else ++num; if (star + 1 > num) { ++sum; ++num; --star; } } printf("%d\n", sum); } return 0; }
相关推荐
极简轻盈高效的纯文本笔记工具软件。如果你需要一款 Windows 上的极简高效的笔记软件,Notation 将会是你很好的选择。而它配合 SimpleNote 又能完美的跨平台使用,使得该软件实用性大大提升。
This document describes the notation for the visual representation of the Unified Modeling Language (UML). This document should be used in conjunction with the companion UML Semantics document. This ...
Introduction to JavaScript Object Notation - Early Release
Notation Player,可以将MIDI文件以乐谱的形式显示和打印。MID音乐格式原理是源文件只提供一串或几串乐谱信息流,一个乐符对应你电脑声卡中的一个标准音,当播放器读取迷笛时,就是一个从声卡里提取、加工、合成工作...
JSON(JavaScript Object Notation) 是一种轻量级的数据交换格式。易于人阅读和编写。同时也易于机器解析和生成。它基于JavaScript Programming Language, Standard ECMA-262 3rd Edition - December 1999的一个子集...
JSON(JavaScript Object Notation) 是一种轻量级的数据交换格式。易于人阅读和编写,同时也易于机器解析和生成。它基于JavaScript(Standard ECMA-262 3rd Edition - December 1999)的一个子集。 JSON采用完全独立...
J. M. Spivey Programming Research Group University of Oxford
业务流程建模标注(Business Process Modeling Notation,BPMN)详细介绍 - BPEL
Notation Jl
Some thoughts on differential equation notation - functional vs classical.pdf
强化学习导论符号摘要,大写字母表示随机变量,反之小写字母表示随机变量的值和标量函数的值。需要为实值向量的量以粗体和小写字母书写(即使是随机变量)。矩阵是粗体大写字母。
provides standard western music notation in Max/MSP (Puckette, Zicarelli). MaxScore supports a rich set of Max messages that allows the user to populate a score with notes, query note properties, ...
The JavaScript Object Notation (JSON) Data Interchange Format,RFC 8259,
a new geometric notation for open and closed-loop robots
一款免费、启动速度足够快、有高效快捷键、可全文搜索的笔记软件,支持批量导入 txt 文档以及 zip 压缩包,也可以将数据导出成 txt 或 html 文件
深度学习文档 Standard notations for Deep Learning This document has the purpose of discussing a new standard for deep learning mathematical notations.
JSON(JavaScriptObject Notation)是一种轻量级的数据交换格式。它基于JavaScript的一个子集。JSON采用完全独立于语言的文本格式,但是也使用了类似于C语言家族的习惯。这些特性使JSON成为理想的数据交换语言。易于人...
目录执照 演示版演示页代码沙箱 安装NPM: npm install --save vue-rough-notation CDN: < script src = "https://unpkg.com/vue-rough-notation/dist/vue-rough-notation.js" > < / script > 用法main.js...
OMG specification Business Process Model and Notation (BPMN)
业务流程建模标注(Business Process Modeling Notation,BPMN) 8种资料打包奉献 BPMN入门教程(From IBM) 使用Visio画BPMN 包括BPMN 2.0 Visio模板元素