L****Y
发帖数: 355 | 1 前两道coding题目不说了，直接上第三道：
Write code to do arithmetic expression validation:
digits: 0..9
operators: +, -, (, )
E.g.:
1+2-3 valid
1+(2-(3+4)) valid
-2 not valid | N*D
发帖数: 3641 | | L****Y
发帖数: 355 | 3 别人就是这么给define的..
【在 N*D 的大作中提到】
: 为什么-2不是valide的呢？
| r*******e
发帖数: 7583 | 4 取决于-的定义，如果这题限定必须是二目运算符，那-2就不行吧
【在 N*D 的大作中提到】
: 为什么-2不是valide的呢？
| r*******e
发帖数: 7583 | 5 这样定义简单。允许负号的话更麻烦
【在 L****Y 的大作中提到】
: 别人就是这么给define的..
| j******2
发帖数: 362 | 6 转换成rpn，再计算，如果(1)最后存数的stack不为空, or (2)op来了stack不够俩数，
就是错的。 | r**h
发帖数: 1288 | 7 请教一下这题的标准做法是什么？
我这种做法可以吗？
数字的下一个valid字符：右括号、操作符、数字
操作符的下一个valid字符：左括号、数字
左括号的下一个valid字符：左括号、数字
右括号的下一个valid字符：右括号、操作符
就和自动机一样检查下一个字符是否valid。同时兼顾检查左右括号的匹配。
【在 L****Y 的大作中提到】
: 前两道coding题目不说了，直接上第三道：
: Write code to do arithmetic expression validation:
: digits: 0..9
: operators: +, -, (, )
: E.g.:
: 1+2-3 valid
: 1+(2-(3+4)) valid
: -2 not valid
| r*******e
发帖数: 7583 | 8 还要检查第一个和最后一个字符是不是valid
【在 r**h 的大作中提到】
: 请教一下这题的标准做法是什么？
: 我这种做法可以吗？
: 数字的下一个valid字符：右括号、操作符、数字
: 操作符的下一个valid字符：左括号、数字
: 左括号的下一个valid字符：左括号、数字
: 右括号的下一个valid字符：右括号、操作符
: 就和自动机一样检查下一个字符是否valid。同时兼顾检查左右括号的匹配。
| r**h
发帖数: 1288 | 9 嗯，再加上边界检查。这样就可以了吗？
【在 r*******e 的大作中提到】
: 还要检查第一个和最后一个字符是不是valid
| w***y
发帖数: 6251 | 10 同问， 逆波兰这种方法，应该不是要求每个人都知道的吧／／汗
我搜出rpn算法还没看太明白呢 | | | y***g
发帖数: 1492 | 11 两个stacks 一个放数 一个放opetator和左括号 碰到右括号pop运算符对top的两个数
运算 结果push进stack 直到碰到左括号
如果数的stack少于两个数无法运算或没有左括号match或最后数的stack里多于一个数
剩下 则不是valid
同问， 逆波兰这种方法，应该不是要求每个人都知道的吧／／汗我搜出rpn算法还没看
太明白呢
【在 w***y 的大作中提到】
: 同问， 逆波兰这种方法，应该不是要求每个人都知道的吧／／汗
: 我搜出rpn算法还没看太明白呢
| c********t
发帖数: 5706 | 12 感觉转RNP有些over kill了，毕竟只是validate.
stack + recursion应该可以解吧，等有空写一下才知道。
【在 L****Y 的大作中提到】
: 前两道coding题目不说了，直接上第三道：
: Write code to do arithmetic expression validation:
: digits: 0..9
: operators: +, -, (, )
: E.g.:
: 1+2-3 valid
: 1+(2-(3+4)) valid
: -2 not valid
| j******2
发帖数: 362 | 13 可以不全转，但流程是一样：
1.用stack记op，push的不是算符而是优先级。
2.用int记num，来一个数num++，处理一个算符num--(-2+1)。
每次来op时检查num>=2，最后检查num==1。
【在 c********t 的大作中提到】
: 感觉转RNP有些over kill了，毕竟只是validate.
: stack + recursion应该可以解吧，等有空写一下才知道。
| w********p
发帖数: 948 | | j*****y
发帖数: 1071 | 15 写了一个，欢迎测试
#include
#include
#include
#include
#include
using namespace std;
bool isNumber(string s)
{
if(s[0] == '+' || s[0] == '-' || s[0] == '(' || s[0] == ')')
{
return false;
}
return true;
}
int helper(int a, int b, char c)
{
if(c == '+')
{
return a + b;
}
else
{
return a - b;
}
}
bool valid(vector &s)
{
stack v;
stack c;
for(int i = 0; i < s.size(); ++i)
{
if(isNumber(s[i]))
{
int num2 = atoi(s[i].c_str());
if(!v.empty() && c.empty())
{
return false;
}
if(!c.empty() && (c.top() == '+' || c.top() == '-'))
{
if(v.empty())
{
return false;
}
int num1 = v.top();
v.pop();
v.push(helper(num1, num2, c.top()));
c.pop();
}
else
{
v.push(num2);
}
}
else if(s[i][0] == '+' || s[i][0] == '-' || s[i][0] == '(')
{
c.push(s[i][0]);
}
else
{
if(c.empty() || c.top() != '(')
{
return false;
}
c.pop();
if(!c.empty() && (c.top() == '+' || c.top() == '-'))
{
if(v.size() < 2)
{
return false;
}
int num2 = v.top();
v.pop();
int num1 = v.top();
v.pop();
v.push(helper(num1, num2, c.top()));
c.pop();
}
}
}
if(!c.empty())
{
return false;
}
return true;
}
int main(int argc, char *argv[])
{
vector s;
for(int i = 1; i < argc; ++i)
{
s.push_back(argv[i]);
}
for(int i = 0; i < s.size(); ++i)
{
cout << s[i] << " ";
}
cout <
cout << valid(s) <
}
【在 L****Y 的大作中提到】
: 前两道coding题目不说了，直接上第三道：
: Write code to do arithmetic expression validation:
: digits: 0..9
: operators: +, -, (, )
: E.g.:
: 1+2-3 valid
: 1+(2-(3+4)) valid
: -2 not valid
| t*********h
发帖数: 941 | 16 RPN其实理解了之后coding不是很麻烦
【在 c********t 的大作中提到】
: 感觉转RNP有些over kill了，毕竟只是validate.
: stack + recursion应该可以解吧，等有空写一下才知道。
| L*********r
发帖数: 9 | 17 I think this approach is good, simple and effective.
【在 r**h 的大作中提到】
: 请教一下这题的标准做法是什么？
: 我这种做法可以吗？
: 数字的下一个valid字符：右括号、操作符、数字
: 操作符的下一个valid字符：左括号、数字
: 左括号的下一个valid字符：左括号、数字
: 右括号的下一个valid字符：右括号、操作符
: 就和自动机一样检查下一个字符是否valid。同时兼顾检查左右括号的匹配。
| x*****0
发帖数: 452 | | r*******e
发帖数: 340 | | r****m
发帖数: 70 | 20 boolean validate(String expression){
String expr = expression.trim();
boolean expectNum = true;
int numOfParentheses = 0;
int i = 0;
while(i < expr.length()){
if(expr.charAt(i) == '('){
if(!expectNum) return false;
numOfParentheses++;
i++;
} else if (expr.charAt(i) == ')'){
if(expectNum || numOfParentheses < 1) return false;
numOfParentheses--;
i++;
} else if(expectNum){
if(!isDigit(expr.charAt(i))){
return false;
}
i++;
while(i < expr.length() && isDigit(expr.charAt(i))){
i++;
}
expectNum = false;
} else {
if(!isOperator(expr.charAt(i))){
return false;
}
i++;
expectNum = true;
}
}
return expectNum == false && numOfParentheses == 0;
}
boolean isDigit(char c){
return c <= '9' && c >= '0';
}
boolean isOperator(char c){
return c == '+' || c == '-' || c == '*' || c == '/';
} | | | n*****g
发帖数: 16 | 21 My version for C#.
static bool IsValidExpression(string expression)
{
Stack stackOperator = new Stack();
Stack stackOperand = new Stack();
int length = expression.Length;
int i;
char opr;
for (i = 0; i < length; ++i)
{
if (expression[i] == '(' || expression[i] == '+' ||
expression[i] == '-' || expression[i] == '*' || expression[i] == '/')
{
stackOperator.Push(expression[i]);
}
else if (expression[i] >= '0' && expression[i] <= '9')
{
stackOperand.Push(expression[i]);
}
else if (expression[i] == ')' || i == length - 1)
{
bool isRightParenthesis = expression[i] == ')';
do
{
if (!GetOperation(stackOperand, stackOperator))
return false;
} while (stackOperator.Count > 0 && stackOperator.Peek()
!= '(');
if (isRightParenthesis)
{
opr = stackOperator.Pop();
if (opr != '(')
return false;
}
}
else
return false;
}
while (stackOperator.Count > 0)
{
if (!GetOperation(stackOperand, stackOperator))
return false;
}
if (stackOperator.Count == 0 && stackOperand.Count == 1)
return true;
return false;
}
static bool GetOperation(Stack stackOperand, Stack
stackOperator)
{
char operand, opr;
if (stackOperand.Count < 2) return false;
if (stackOperator.Count < 1) return false;
operand = stackOperand.Pop();
if (operand == null)
{
return false;
}
opr = stackOperator.Pop();
if (opr == null || opr == '(')
return false;
operand = stackOperand.Pop();
if (operand == null)
{
return false;
}
stackOperand.Push('0');
return true;
}
【在 L****Y 的大作中提到】
: 前两道coding题目不说了，直接上第三道：
: Write code to do arithmetic expression validation:
: digits: 0..9
: operators: +, -, (, )
: E.g.:
: 1+2-3 valid
: 1+(2-(3+4)) valid
: -2 not valid
| o*****n
发帖数: 189 | 22 import sys
a=sys.argv[1]
op=['+','-']
good=['+','-', '(',')','0','1','2','3','4','5','6','7','8','9']
bad=['()','++','-+','+-','-)','+)',')0',')1',')2',')3',')4',')5',')6',')7','
)8',')9']
def invalid(str):
print "Invalid:", str
exit()
if a[0] in op or a[-1] in op : invalid(a)
for b in bad:
if b in a: invalid(a)
pas=0 # number of (
pae=0 # number of ), pae can not be larger than pas
for s in a:
if s =='(': pas+=1
elif s ==')': pae+=1
if pae > pas : invalid(a)
if s not in good: invalid(a)
if pas != pae: invalid(a)
print a, ": is valid" | f****e
发帖数: 34 | 23 算法有问题,
(1+2)(3+4)被判定为valid了。
我把这题加到oj了 http://www.itint5.com/oj/#41 。
,'
【在 o*****n 的大作中提到】
: import sys
: a=sys.argv[1]
: op=['+','-']
: good=['+','-', '(',')','0','1','2','3','4','5','6','7','8','9']
: bad=['()','++','-+','+-','-)','+)',')0',')1',')2',')3',')4',')5',')6',')7','
: )8',')9']
: def invalid(str):
: print "Invalid:", str
: exit()
: if a[0] in op or a[-1] in op : invalid(a)
| o*****n
发帖数: 189 | 24 # 非常感谢! 加了')('.穷举法简单, 就是容易漏点. :P
import sys
a=sys.argv[1]
op=['+','-']
good=['+','-', '(',')','0','1','2','3','4','5','6','7','8','9']
bad=['()','++','-+','+-','-)','+)',')0',')1',')2',')3',')4',')5',')6',')7','
)8',')9',')(']
def invalid(str):
print "Invalid:", str
exit()
if a[0] in op or a[-1] in op : invalid(a)
for b in bad:
if b in a: invalid(a)
pas=0 # number of (
pae=0 # number of ), pae can not be larger than pas
for s in a:
if s =='(': pas+=1
elif s ==')': pae+=1
if pae > pas : invalid(a)
if s not in good: invalid(a)
if pas != pae: invalid(a)
print a, ": is valid" | d****n
发帖数: 1241 | 25 可以使用编译器在lexing和parsing的时候用的某种技术：recursive descent parsing
http://en.wikipedia.org/wiki/Recursive_descent_parser
下边的代码假设单个的数字也是合法的，比如：
1 合法
（1）合法
(1) + (2) 合法, 等等
#include
#include
#include
#include
using namespace std;
enum TokenKind {
TOK_Unknown = -1,
TOK_End,
TOK_Op,
TOK_LParen,
TOK_RParen,
TOK_Num,
};
static TokenKind getToken(const string &Input, int &Pos)
{
assert(Pos <= Input.length());
char TheChar = Input[Pos];
while (isspace(TheChar)) {
Pos++;
TheChar = Input[Pos];
}
if (isdigit(TheChar)) {
do {
Pos++;
TheChar = Input[Pos];
} while(isdigit(TheChar));
return TOK_Num;
}
TokenKind Tok;
if (TheChar == '(') {
Tok = TOK_LParen;
}
else if (TheChar == ')') {
Tok = TOK_RParen;
}
else if ((TheChar == '+') || (TheChar == '-')) {
Tok = TOK_Op;
}
else if (TheChar == '\0') {
Tok = TOK_End;
}
else {
Tok = TOK_Unknown;
}
Pos++;
return Tok;
}
static TokenKind CurrentToken;
static TokenKind getNextToken(const string &Input, int &Pos)
{
return CurrentToken = getToken(Input, Pos);
}
static bool isExpr(const string &Input, int &Pos);
static bool isParenExpr(const string &Input, int &Pos)
{
// eat '('
getNextToken(Input, Pos);
if (!isExpr(Input, Pos))
return false;
if (CurrentToken != TOK_RParen)
return false;
// eat ')'
getNextToken(Input, Pos);
return true;
}
static bool isNum(const string &Input, int &Pos)
{
if (CurrentToken == TOK_Num) {
// eat the number
getNextToken(Input, Pos);
return true;
}
else {
return false;
}
}
static bool isPrimaryExpr(const string &Input, int &Pos)
{
if (CurrentToken == TOK_LParen)
return isParenExpr(Input, Pos);
return isNum(Input, Pos);
}
static bool isExpr(const string &Input, int &Pos)
{
if (!isPrimaryExpr(Input, Pos))
return false;
if (CurrentToken != TOK_Op)
return true;
// eat '+' or '-'
getNextToken(Input, Pos);
return isExpr(Input, Pos);
}
int main(int argc, char *argv[])
{
assert((argc == 2) && "Please pass a string!");
int Pos = 0;
string Input(argv[1]);
getNextToken(Input, Pos);
if (isExpr(Input, Pos) && (CurrentToken == TOK_End))
cout << "valid\n";
else
cout << "invalid\n";
return 0;
} | L****Y
发帖数: 355 | 26 前两道coding题目不说了，直接上第三道：
Write code to do arithmetic expression validation:
digits: 0..9
operators: +, -, (, )
E.g.:
1+2-3 valid
1+(2-(3+4)) valid
-2 not valid | N*D
发帖数: 3641 | | L****Y
发帖数: 355 | 28 别人就是这么给define的..
【在 N*D 的大作中提到】
: 为什么-2不是valide的呢？
| r*******e
发帖数: 7583 | 29 取决于-的定义，如果这题限定必须是二目运算符，那-2就不行吧
【在 N*D 的大作中提到】
: 为什么-2不是valide的呢？
| r*******e
发帖数: 7583 | 30 这样定义简单。允许负号的话更麻烦
【在 L****Y 的大作中提到】
: 别人就是这么给define的..
| | | j******2
发帖数: 362 | 31 转换成rpn，再计算，如果(1)最后存数的stack不为空, or (2)op来了stack不够俩数，
就是错的。 | r**h
发帖数: 1288 | 32 请教一下这题的标准做法是什么？
我这种做法可以吗？
数字的下一个valid字符：右括号、操作符、数字
操作符的下一个valid字符：左括号、数字
左括号的下一个valid字符：左括号、数字
右括号的下一个valid字符：右括号、操作符
就和自动机一样检查下一个字符是否valid。同时兼顾检查左右括号的匹配。
【在 L****Y 的大作中提到】
: 前两道coding题目不说了，直接上第三道：
: Write code to do arithmetic expression validation:
: digits: 0..9
: operators: +, -, (, )
: E.g.:
: 1+2-3 valid
: 1+(2-(3+4)) valid
: -2 not valid
| r*******e
发帖数: 7583 | 33 还要检查第一个和最后一个字符是不是valid
【在 r**h 的大作中提到】
: 请教一下这题的标准做法是什么？
: 我这种做法可以吗？
: 数字的下一个valid字符：右括号、操作符、数字
: 操作符的下一个valid字符：左括号、数字
: 左括号的下一个valid字符：左括号、数字
: 右括号的下一个valid字符：右括号、操作符
: 就和自动机一样检查下一个字符是否valid。同时兼顾检查左右括号的匹配。
| r**h
发帖数: 1288 | 34 嗯，再加上边界检查。这样就可以了吗？
【在 r*******e 的大作中提到】
: 还要检查第一个和最后一个字符是不是valid
| w***y
发帖数: 6251 | 35 同问， 逆波兰这种方法，应该不是要求每个人都知道的吧／／汗
我搜出rpn算法还没看太明白呢 | y***g
发帖数: 1492 | 36 两个stacks 一个放数 一个放opetator和左括号 碰到右括号pop运算符对top的两个数
运算 结果push进stack 直到碰到左括号
如果数的stack少于两个数无法运算或没有左括号match或最后数的stack里多于一个数
剩下 则不是valid
同问， 逆波兰这种方法，应该不是要求每个人都知道的吧／／汗我搜出rpn算法还没看
太明白呢
【在 w***y 的大作中提到】
: 同问， 逆波兰这种方法，应该不是要求每个人都知道的吧／／汗
: 我搜出rpn算法还没看太明白呢
| c********t
发帖数: 5706 | 37 感觉转RNP有些over kill了，毕竟只是validate.
stack + recursion应该可以解吧，等有空写一下才知道。
【在 L****Y 的大作中提到】
: 前两道coding题目不说了，直接上第三道：
: Write code to do arithmetic expression validation:
: digits: 0..9
: operators: +, -, (, )
: E.g.:
: 1+2-3 valid
: 1+(2-(3+4)) valid
: -2 not valid
| j******2
发帖数: 362 | 38 可以不全转，但流程是一样：
1.用stack记op，push的不是算符而是优先级。
2.用int记num，来一个数num++，处理一个算符num--(-2+1)。
每次来op时检查num>=2，最后检查num==1。
【在 c********t 的大作中提到】
: 感觉转RNP有些over kill了，毕竟只是validate.
: stack + recursion应该可以解吧，等有空写一下才知道。
| w********p
发帖数: 948 | | j*****y
发帖数: 1071 | 40 写了一个，欢迎测试
#include
#include
#include
#include
#include
using namespace std;
bool isNumber(string s)
{
if(s[0] == '+' || s[0] == '-' || s[0] == '(' || s[0] == ')')
{
return false;
}
return true;
}
int helper(int a, int b, char c)
{
if(c == '+')
{
return a + b;
}
else
{
return a - b;
}
}
bool valid(vector &s)
{
stack v;
stack c;
for(int i = 0; i < s.size(); ++i)
{
if(isNumber(s[i]))
{
int num2 = atoi(s[i].c_str());
if(!v.empty() && c.empty())
{
return false;
}
if(!c.empty() && (c.top() == '+' || c.top() == '-'))
{
if(v.empty())
{
return false;
}
int num1 = v.top();
v.pop();
v.push(helper(num1, num2, c.top()));
c.pop();
}
else
{
v.push(num2);
}
}
else if(s[i][0] == '+' || s[i][0] == '-' || s[i][0] == '(')
{
c.push(s[i][0]);
}
else
{
if(c.empty() || c.top() != '(')
{
return false;
}
c.pop();
if(!c.empty() && (c.top() == '+' || c.top() == '-'))
{
if(v.size() < 2)
{
return false;
}
int num2 = v.top();
v.pop();
int num1 = v.top();
v.pop();
v.push(helper(num1, num2, c.top()));
c.pop();
}
}
}
if(!c.empty())
{
return false;
}
return true;
}
int main(int argc, char *argv[])
{
vector s;
for(int i = 1; i < argc; ++i)
{
s.push_back(argv[i]);
}
for(int i = 0; i < s.size(); ++i)
{
cout << s[i] << " ";
}
cout <
cout << valid(s) <
}
【在 L****Y 的大作中提到】
: 前两道coding题目不说了，直接上第三道：
: Write code to do arithmetic expression validation:
: digits: 0..9
: operators: +, -, (, )
: E.g.:
: 1+2-3 valid
: 1+(2-(3+4)) valid
: -2 not valid
| | | t*********h
发帖数: 941 | 41 RPN其实理解了之后coding不是很麻烦
【在 c********t 的大作中提到】
: 感觉转RNP有些over kill了，毕竟只是validate.
: stack + recursion应该可以解吧，等有空写一下才知道。
| L*********r
发帖数: 9 | 42 I think this approach is good, simple and effective.
【在 r**h 的大作中提到】
: 请教一下这题的标准做法是什么？
: 我这种做法可以吗？
: 数字的下一个valid字符：右括号、操作符、数字
: 操作符的下一个valid字符：左括号、数字
: 左括号的下一个valid字符：左括号、数字
: 右括号的下一个valid字符：右括号、操作符
: 就和自动机一样检查下一个字符是否valid。同时兼顾检查左右括号的匹配。
| x*****0
发帖数: 452 | | r*******e
发帖数: 340 | | r****m
发帖数: 70 | 45 boolean validate(String expression){
String expr = expression.trim();
boolean expectNum = true;
int numOfParentheses = 0;
int i = 0;
while(i < expr.length()){
if(expr.charAt(i) == '('){
if(!expectNum) return false;
numOfParentheses++;
i++;
} else if (expr.charAt(i) == ')'){
if(expectNum || numOfParentheses < 1) return false;
numOfParentheses--;
i++;
} else if(expectNum){
if(!isDigit(expr.charAt(i))){
return false;
}
i++;
while(i < expr.length() && isDigit(expr.charAt(i))){
i++;
}
expectNum = false;
} else {
if(!isOperator(expr.charAt(i))){
return false;
}
i++;
expectNum = true;
}
}
return expectNum == false && numOfParentheses == 0;
}
boolean isDigit(char c){
return c <= '9' && c >= '0';
}
boolean isOperator(char c){
return c == '+' || c == '-' || c == '*' || c == '/';
} | n*****g
发帖数: 16 | 46 My version for C#.
static bool IsValidExpression(string expression)
{
Stack stackOperator = new Stack();
Stack stackOperand = new Stack();
int length = expression.Length;
int i;
char opr;
for (i = 0; i < length; ++i)
{
if (expression[i] == '(' || expression[i] == '+' ||
expression[i] == '-' || expression[i] == '*' || expression[i] == '/')
{
stackOperator.Push(expression[i]);
}
else if (expression[i] >= '0' && expression[i] <= '9')
{
stackOperand.Push(expression[i]);
}
else if (expression[i] == ')' || i == length - 1)
{
bool isRightParenthesis = expression[i] == ')';
do
{
if (!GetOperation(stackOperand, stackOperator))
return false;
} while (stackOperator.Count > 0 && stackOperator.Peek()
!= '(');
if (isRightParenthesis)
{
opr = stackOperator.Pop();
if (opr != '(')
return false;
}
}
else
return false;
}
while (stackOperator.Count > 0)
{
if (!GetOperation(stackOperand, stackOperator))
return false;
}
if (stackOperator.Count == 0 && stackOperand.Count == 1)
return true;
return false;
}
static bool GetOperation(Stack stackOperand, Stack
stackOperator)
{
char operand, opr;
if (stackOperand.Count < 2) return false;
if (stackOperator.Count < 1) return false;
operand = stackOperand.Pop();
if (operand == null)
{
return false;
}
opr = stackOperator.Pop();
if (opr == null || opr == '(')
return false;
operand = stackOperand.Pop();
if (operand == null)
{
return false;
}
stackOperand.Push('0');
return true;
}
【在 L****Y 的大作中提到】
: 前两道coding题目不说了，直接上第三道：
: Write code to do arithmetic expression validation:
: digits: 0..9
: operators: +, -, (, )
: E.g.:
: 1+2-3 valid
: 1+(2-(3+4)) valid
: -2 not valid
| o*****n
发帖数: 189 | 47 import sys
a=sys.argv[1]
op=['+','-']
good=['+','-', '(',')','0','1','2','3','4','5','6','7','8','9']
bad=['()','++','-+','+-','-)','+)',')0',')1',')2',')3',')4',')5',')6',')7','
)8',')9']
def invalid(str):
print "Invalid:", str
exit()
if a[0] in op or a[-1] in op : invalid(a)
for b in bad:
if b in a: invalid(a)
pas=0 # number of (
pae=0 # number of ), pae can not be larger than pas
for s in a:
if s =='(': pas+=1
elif s ==')': pae+=1
if pae > pas : invalid(a)
if s not in good: invalid(a)
if pas != pae: invalid(a)
print a, ": is valid" | f****e
发帖数: 34 | 48 算法有问题,
(1+2)(3+4)被判定为valid了。
我把这题加到oj了 http://www.itint5.com/oj/#41 。
,'
【在 o*****n 的大作中提到】
: import sys
: a=sys.argv[1]
: op=['+','-']
: good=['+','-', '(',')','0','1','2','3','4','5','6','7','8','9']
: bad=['()','++','-+','+-','-)','+)',')0',')1',')2',')3',')4',')5',')6',')7','
: )8',')9']
: def invalid(str):
: print "Invalid:", str
: exit()
: if a[0] in op or a[-1] in op : invalid(a)
| o*****n
发帖数: 189 | 49 # 非常感谢! 加了')('.穷举法简单, 就是容易漏点. :P
import sys
a=sys.argv[1]
op=['+','-']
good=['+','-', '(',')','0','1','2','3','4','5','6','7','8','9']
bad=['()','++','-+','+-','-)','+)',')0',')1',')2',')3',')4',')5',')6',')7','
)8',')9',')(']
def invalid(str):
print "Invalid:", str
exit()
if a[0] in op or a[-1] in op : invalid(a)
for b in bad:
if b in a: invalid(a)
pas=0 # number of (
pae=0 # number of ), pae can not be larger than pas
for s in a:
if s =='(': pas+=1
elif s ==')': pae+=1
if pae > pas : invalid(a)
if s not in good: invalid(a)
if pas != pae: invalid(a)
print a, ": is valid" | d****n
发帖数: 1241 | 50 可以使用编译器在lexing和parsing的时候用的某种技术：recursive descent parsing
http://en.wikipedia.org/wiki/Recursive_descent_parser
下边的代码假设单个的数字也是合法的，比如：
1 合法
（1）合法
(1) + (2) 合法, 等等
#include
#include
#include
#include
using namespace std;
enum TokenKind {
TOK_Unknown = -1,
TOK_End,
TOK_Op,
TOK_LParen,
TOK_RParen,
TOK_Num,
};
static TokenKind getToken(const string &Input, int &Pos)
{
assert(Pos <= Input.length());
char TheChar = Input[Pos];
while (isspace(TheChar)) {
Pos++;
TheChar = Input[Pos];
}
if (isdigit(TheChar)) {
do {
Pos++;
TheChar = Input[Pos];
} while(isdigit(TheChar));
return TOK_Num;
}
TokenKind Tok;
if (TheChar == '(') {
Tok = TOK_LParen;
}
else if (TheChar == ')') {
Tok = TOK_RParen;
}
else if ((TheChar == '+') || (TheChar == '-')) {
Tok = TOK_Op;
}
else if (TheChar == '\0') {
Tok = TOK_End;
}
else {
Tok = TOK_Unknown;
}
Pos++;
return Tok;
}
static TokenKind CurrentToken;
static TokenKind getNextToken(const string &Input, int &Pos)
{
return CurrentToken = getToken(Input, Pos);
}
static bool isExpr(const string &Input, int &Pos);
static bool isParenExpr(const string &Input, int &Pos)
{
// eat '('
getNextToken(Input, Pos);
if (!isExpr(Input, Pos))
return false;
if (CurrentToken != TOK_RParen)
return false;
// eat ')'
getNextToken(Input, Pos);
return true;
}
static bool isNum(const string &Input, int &Pos)
{
if (CurrentToken == TOK_Num) {
// eat the number
getNextToken(Input, Pos);
return true;
}
else {
return false;
}
}
static bool isPrimaryExpr(const string &Input, int &Pos)
{
if (CurrentToken == TOK_LParen)
return isParenExpr(Input, Pos);
return isNum(Input, Pos);
}
static bool isExpr(const string &Input, int &Pos)
{
if (!isPrimaryExpr(Input, Pos))
return false;
if (CurrentToken != TOK_Op)
return true;
// eat '+' or '-'
getNextToken(Input, Pos);
return isExpr(Input, Pos);
}
int main(int argc, char *argv[])
{
assert((argc == 2) && "Please pass a string!");
int Pos = 0;
string Input(argv[1]);
getNextToken(Input, Pos);
if (isExpr(Input, Pos) && (CurrentToken == TOK_End))
cout << "valid\n";
else
cout << "invalid\n";
return 0;
} | | | n******n
发帖数: 567 | | y****a
发帖数: 15 | 52 RPN显然是可以的，而且效率高。逆波兰表达式看起来是不应该要求人人都会，但是考
起来真的概率很高。
或者按照写interpreter的思路，定义一套规则：
exp := (exp)
|= exp operator exp
|= num
做recursive validation | g*********e
发帖数: 14401 | 53 re
【在 r*******e 的大作中提到】
: 这样定义简单。允许负号的话更麻烦
| d****n
发帖数: 233 | 54 bool isDigit(const string &expr, int pos)
{
return expr[pos] >='0' && expr[pos] <= '9';
}
void parseNum(const string &expr, int &pos)
{
if (expr[pos] == '0') {
pos++;
// if the first char is '0', it is a number
// following digits should be treated as separate number.
return;
}
while(isDigit(expr, pos))
pos++;
return;
}
bool validate(const string& expr) {
stack st;
int i = 0;
while(i < expr.length()) {
if(isDigit(expr, i)) {
parseNum(expr, i);
// if current is a number
// compact the stack until it's empty
// or a '(' is seen)
while(st.size() > 0 && (st.top() == '+' || st.top() == '-')){
st.pop();
if (st.size() ==0 || st.top() != 'N')
return false;
st.pop();
}
// push current number
st.push('N');
}
else if(expr[i] == ')') {
// ')' has to follow a number in the stack
if (st.size() == 0 || st.top() != 'N')
return false;
st.pop();
// Before the number, there must be a '(')
if (st.size() == 0 || st.top() != '(')
return false;
st.pop();
// compact the stack until it's empty
// or a '(' is seen)
while(st.size() > 0 && (st.top() == '+' || st.top() == '-')){
st.pop();
if (st.size() ==0 || st.top() != 'N')
return false;
st.pop();
}
// push current number
st.push('N');
i++;
}
else {
st.push(expr[i]);
i++;
}
}
return st.size() == 1;
}
【在 g*********e 的大作中提到】
: re
| w**t
发帖数: 893 | 55 exp : op (+/-OP)*
OP : d
| '('exp')'
这样好处里写吧
【在 y****a 的大作中提到】
: RPN显然是可以的，而且效率高。逆波兰表达式看起来是不应该要求人人都会，但是考
: 起来真的概率很高。
: 或者按照写interpreter的思路，定义一套规则：
: exp := (exp)
: |= exp operator exp
: |= num
: 做recursive validation
|
|
