首页 > 代码库 > poj1068 Parencodings
poj1068 Parencodings
这题分两步,第一步由给定的p字符串得到原来的括号表达式,第二步由括号表达式得到W字符串。
q By an integer sequence P = p1 p2...pn where pi is the number of left parentheses before the ith right parenthesis in S (P-sequence).
第一步重建过程很直观,遍历整个P数组,每个数肯定对应于一个右括号,就是在它前面加几个左括号的问题,按照定义,若将P数组第一位补一个0,则第i个数需要加的左括号数目就是
p[i] - p[i - 1]
第二步用到栈,遍历第一步得到的括号字符串,如果是左括号,入栈,如果是右括号,当然是从栈中弹出一个左括号,问题是现在输出的是什么(也就是在匹配它的左括号之前出现了多少右括号),再想,匹配左括号之前出现的右括号数目,也就是该右括号与它的左括号之间包含的括号对数,更进一步,也就是在自己的左括号压栈之后总共匹配的括号对数目。
如果只是在每次遇到右括号的时候弹出,就无法记录左右括号之间共匹配了多少对,于是想到每次匹配一对,就往栈中压入一个‘*’作为标记,于是在匹配自己的左括号的时候,弹出多少‘*’,就是左右括号之间出现的匹配对数。
#include<iostream>#include<string>#include<stack>using namespace std;int main(){#ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin);#endif int t; scanf("%d", &t); for (int i = 0; i < t; i++){ int n; scanf("%d", &n); string s; int last = 0; int j; for (j = 0; j < n; j++){ int m; scanf("%d", &m); for (int k = 0; k < m - last; k++){ s.push_back(‘(‘); } s.push_back(‘)‘); last = m; } stack<char> st; for (string::iterator it = s.begin(); it != s.end(); it++){ if (*it == ‘(‘){ st.push(‘(‘); } else { int w = 1; while (st.top() != ‘(‘ ){ st.pop(); w++; } st.pop(); for (int i = 0; i < w; i++){ st.push(‘*‘); } printf("%d ", w); } } printf("\n"); }}
poj1068 Parencodings
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。