可以将文章内容翻译成中文,广告屏蔽插件可能会导致该功能失效(如失效,请关闭广告屏蔽插件后再试):
问题:
I am trying to make a calculator in C or Objective-C that accepts a string along the lines of
8/2+4(3*9)^2
and returns the answer 2920. I would prefer not to use a generator like Lex or Yacc, so I want to code it from the ground up. How should I go about doing this? Other than the Dragon book, are there any recommended texts that cover this subject matter?
回答1:
Try this:
http://en.wikipedia.org/wiki/Shunting-yard_algorithm
回答2:
Dave DeLong's DDMathParser class may save you a lot of time and trouble.
回答3:
If I remember correctly, you can solve this problem with two stacks, one for the operators, the other for the operands.
// OPTR stack: store operators
// OPND stack: store operands
// OP: predefined set of operators
OperandType EvaluateExpression(){
InitStack(OPET);Push(OPTR,'#');
initStack(OPND);c=getchar();
while(c!='#'||GetTop(OPTR)!='#'){
if(!In(c,OP)){Push((OPND,c);c=getchar();} //Push to stack if not operator
else
switch(Precede(GetTop(OPTR),c){
//Top element in stack has a lower priority
case '<':
Push(OPTR,c); c=getch();
break;
case '=':
Pop(OPTR,x); c=getch();
break;
//Pop top element and push back the calculated result
case '>':
Pop(OPTR,theta);
Pop(OPND,b); Pop(OPND,a);
Push(OPND,Operate(a,theta,b));
break;
}
}
return GetTop(OPND);
}
回答4:
The shunting yard algorithm has already been mentioned. The other classic one is simple recursive descent. Here's a fairly short one I wrote many years ago:
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
void expression(void);
void show(int ch) {
putchar(ch);
putchar(' ');
}
int token() {
int ch;
while (isspace(ch=getchar()))
;
return ch;
}
void factor() {
int ch = token();
if (ch == '(') {
expression();
ch = token();
if (ch != ')') {
fprintf(stderr, "Syntax error. Expected close paren, found: %c\n", ch);
exit(EXIT_FAILURE);
}
}
else
show(ch);
}
void term() {
int ch;
factor();
ch = token();
if (ch == '*' || ch == '/') {
term();
show(ch);
}
else
ungetc(ch, stdin);
}
void expression() {
int ch;
term();
ch = token();
if (ch == '-' || ch=='+') {
expression();
show(ch);
}
else
ungetc(ch, stdin);
}
int main(int argc, char **argv) {
expression();
return 0;
}
Note that this particular one just parses input, and converts it to RPN form. If you want to interpret the result instead, you'd replace printing out each operand/operator with actually evaluating the result of that part of the expression.
回答5:
I think this close to what you want:
http://www.codeproject.com/KB/recipes/alxparser.aspx
回答6:
I did this in CSE340: Introduction to Programming Lanugages in my Junior year of CS in college. So if you really want to code up a parser from scratch, be prepared that it could be "a semester long project."
You'll need to tokenize, parse, build an abstract expression tree, evaluate, etc.
We used Louden's Programming Languages: Principles and Practice. I liked it. Though it didn't do the best job of walking you through the implementation process.
Of course, this would be more than "coding up from scratch." You'd need to make a grammar, then build a parser to process the rules...aside from a learning activity, I'm not sure why you'd wanna do this.
回答7:
using Objective-C NSLinguisticTagger may be a good solution
- (void)enumerateTagsInRange:(NSRange)range
scheme:(NSString *)tagScheme
options:(NSLinguisticTaggerOptions)opts
usingBlock:(void (^)(NSString *tag, NSRange tokenRange, NSRange sentenceRange, BOOL *stop))block