Parsing/RPN calculator algorithm: Difference between revisions
m
→{{header|Wren}}: Minor tidy
(→{{header|QuickBASIC}}: Added a solution.) |
m (→{{header|Wren}}: Minor tidy) |
||
| (4 intermediate revisions by 3 users not shown) | |||
Line 680:
=={{header|BASIC}}==
==={{header|ANSI
{{works with|Decimal BASIC}}
<syntaxhighlight lang="basic">1000 DECLARE EXTERNAL SUB rpn
Line 975:
Token: / Operation / Stack <--- 0.0001220703125 3
Token: + Operation + Stack <--- 3.0001220703125
</pre>
=== {{header|GW-BASIC}} ===
{{trans|QuickBASIC}}
Supports multi-digit numbers and negative numbers.
{{works with|BASICA}}
<syntaxhighlight lang="gwbasic">
10 REM Parsing/RPN calculator algorithm
20 MAX.INDEX% = 63
30 REM Stack
40 REM TOP.INDEX% - top index of the stack
50 DIM ELEMS(MAX.INDEX%)
60 EXPR$ = "3 4 2 * 1 5 - 2 3 ^ ^ / +": GOSUB 200
70 END
190 REM ** Evaluate the expression in RPN
200 GOSUB 1000
210 PRINT "Input", "Operation", "Stack after"
220 REM SP% - start position of token, DP% - position of delimiter
230 DP% = 0
240 REM Loop: do ... until DP% = 0
250 SP% = DP% + 1
260 DP% = INSTR(DP% + 1, EXPR$, " ")
270 IF DP% = 0 THEN TOKEN$ = MID$(EXPR$, SP%, LEN(EXPR$) - SP% + 1) ELSE TE% = DP% - 1: TOKEN$ = MID$(EXPR$, SP%, DP% - SP%)
280 PRINT TOKEN$,
290 IF TOKEN$ <> "*" THEN 350
300 PRINT "Operate",
310 GOSUB 1060: SECOND = POP
320 GOSUB 1060: FIRST = POP
330 X = FIRST * SECOND: GOSUB 1160
340 GOTO 610
350 IF TOKEN$ <> "/" THEN 410
360 PRINT "Operate",
370 GOSUB 1060: SECOND = POP
380 GOSUB 1060: FIRST = POP
390 X = FIRST / SECOND: GOSUB 1160
400 GOTO 610
410 IF TOKEN$ <> "-" THEN 470
420 PRINT "Operate",
430 GOSUB 1060: SECOND = POP
440 GOSUB 1060: FIRST = POP
450 X = FIRST - SECOND: GOSUB 1160
460 GOTO 610
470 IF TOKEN$ <> "+" THEN 530
480 PRINT "Operate",
490 GOSUB 1060: SECOND = POP
500 GOSUB 1060: FIRST = POP
510 X = FIRST + SECOND: GOSUB 1160
520 GOTO 610
530 IF TOKEN$ <> "^" THEN 590
540 PRINT "Operate",
550 GOSUB 1060: SECOND = POP
560 GOSUB 1060: FIRST = POP
570 X = FIRST ^ SECOND: GOSUB 1160
580 GOTO 610
590 PRINT "Push",
600 X = VAL(TOKEN$): GOSUB 1160
610 GOSUB 1100
620 IF DP% <> 0 THEN 250
630 GOSUB 1060:
640 PRINT "Final answer: "; POP
650 GOSUB 1030
660 IF NOT EMPTY% THEN PRINT "Error, too many operands: "; : GOSUB 1100: STOP
670 RETURN
980 REM ** Operations on the stack
990 REM ** Make the stack empty
1000 TOP.INDEX% = MAX.INDEX% + 1
1010 RETURN
1020 REM ** Is the stack empty?
1030 EMPTY% = TOP.INDEX% > MAX.INDEX%
1040 RETURN
1050 REM ** Pop from the stack
1060 GOSUB 1030
1070 IF NOT EMPTY% THEN POP = ELEMS(TOP.INDEX%): TOP.INDEX% = TOP.INDEX% + 1 ELSE PRINT "The stack is empty.": STOP
1080 RETURN
1090 REM ** Print the stack
1100 FOR PTR% = TOP.INDEX% TO MAX.INDEX%
1110 PRINT USING "######.###"; ELEMS(PTR%);
1120 NEXT PTR%
1130 PRINT
1140 RETURN
1150 REM ** Push to the stack
1160 IF TOP.INDEX% > 0 THEN TOP.INDEX% = TOP.INDEX% - 1: ELEMS(TOP.INDEX%) = X ELSE PRINT "The stack is full.": STOP
1170 RETURN
</syntaxhighlight>
{{out}}
<pre>
Input Operation Stack after
3 Push 3.000
4 Push 4.000 3.000
2 Push 2.000 4.000 3.000
* Operate 8.000 3.000
1 Push 1.000 8.000 3.000
5 Push 5.000 1.000 8.000 3.000
- Operate -4.000 8.000 3.000
2 Push 2.000 -4.000 8.000 3.000
3 Push 3.000 2.000 -4.000 8.000 3.000
^ Operate 8.000 -4.000 8.000 3.000
^ Operate 65536.000 8.000 3.000
/ Operate 0.000 3.000
+ Operate 3.000
Final answer: 3.000122
</pre>
Line 2,319 ⟶ 2,420:
The final value is 3.00012</pre>
=={{header|Delphi}}==
{{works with|Delphi|6.0}}
{{libheader|SysUtils,StdCtrls}}
This is a good example of creating s simple object to create a stakc for use in parsing the data.
<syntaxhighlight lang="Delphi">
{This code normally exists in a library, but is presented here for clarity}
function ExtractToken(S: string; Sep: char; var P: integer): string;
{Extract token from S, starting at P up to but not including Sep}
{Terminates with P pointing past Sep or past end of string}
var C: char;
begin
Result:='';
while P<=Length(S) do
begin
C:=S[P]; Inc(P);
if C=Sep then break
else Result:=Result+C;
end;
end;
{Create stack object to handle parsing}
type TRealStack = class(TObject)
private
Data: array of double;
protected
public
function GetStackStr: string;
procedure Push(D: double);
function Pop: double;
end;
procedure TRealStack.Push(D: double);
{Push double on stack}
begin
SetLength(Data,Length(Data)+1);
Data[High(Data)]:=D;
end;
function TRealStack.Pop: double;
{Pop double off stack, raises exception if stack empty}
begin
if Length(Data)<1 then raise exception.Create('Stack Empty');
Result:=Data[High(Data)];
SetLength(Data,Length(Data)-1);
end;
function TRealStack.GetStackStr: string;
{Get string representation of stack data}
var I: integer;
begin
Result:='';
for I:=0 to High(Data) do
begin
if I<>0 then Result:=Result+', ';
Result:=Result+FloatToStrF(Data[I],ffGeneral,18,4);
end;
end;
procedure RPNParser(Memo: TMemo; S: string);
{Parse RPN string and display all operations}
var I: integer;
var Stack: TRealStack;
var Token: string;
var D: double;
function HandleOperator(S: string): boolean;
{Handle numerical operator command}
var Arg1,Arg2: double;
begin
Result:=False;
{Empty comand string? }
if Length(S)>1 then exit;
{Invalid command? }
if not (S[1] in ['+','-','*','/','^']) then exit;
{Get arguments off stack}
Arg1:=Stack.Pop; Arg2:=Stack.Pop;
Result:=True;
{Decode command}
case S[1] of
'+': Stack.Push(Arg2 + Arg1);
'-': Stack.Push(Arg2 - Arg1);
'*': Stack.Push(Arg2 * Arg1);
'/': Stack.Push(Arg2 / Arg1);
'^': Stack.Push(Power(Arg2,Arg1));
else Result:=False;
end;
end;
begin
Stack:=TRealStack.Create;
try
I:=1;
while true do
begin
{Extract one token from string}
Token:=ExtractToken(S,' ',I);
{Exit if no more data}
if Token='' then break;
{If token is a number convert it to a double otherwise, process an operator}
if Token[1] in ['0'..'9'] then Stack.Push(StrToFloat(Token))
else if not HandleOperator(Token) then raise Exception.Create('Illegal Token: '+Token);
Memo.Lines.Add(Token+' ['+Stack.GetStackStr+']');
end;
finally Stack.Free; end;
end;
procedure ShowRPNParser(Memo: TMemo);
var S: string;
begin
S:='3 4 2 * 1 5 - 2 3 ^ ^ / + ';
RPNParser(Memo,S);
end;
</syntaxhighlight>
{{out}}
<pre>
3 [3]
4 [3, 4]
2 [3, 4, 2]
* [3, 8]
1 [3, 8, 1]
5 [3, 8, 1, 5]
- [3, 8, -4]
2 [3, 8, -4, 2]
3 [3, 8, -4, 2, 3]
^ [3, 8, -4, 8]
^ [3, 8, 65536]
/ [3, 0.0001220703125]
+ [3.0001220703125]
Elapsed Time: 16.409 ms.
</pre>
=={{header|EchoLisp}}==
Line 5,473 ⟶ 5,719:
'''output''' is identical to the 2<sup>nd</sup> REXX version.
<br><br>
=={{header|RPL}}==
'''Straightforward '''
"3 4 2 * 1 5 - 2 3 ^ ^ / +" STR→
{{out}}
<pre>
1: 3.00012207031
</pre>
'''Step-by-step'''
<code>LEXER</code> is defined at [[Parsing/Shunting-yard algorithm#RPL|Parsing/Shunting-yard algorithm]]
{{works with|Halcyon Calc|4.2.7}}
≪ <span style="color:blue">LEXER</span> "" { } 0 → postfix token steps depth
≪ 1 postfix SIZE '''FOR''' j
postfix j GET 'token' STO
'''IF''' token TYPE '''THEN'''
"≪" token + "≫" + STR→ EVAL
depth 1 - ‘depth’ STO
'''ELSE'''
token
depth 1 + ‘depth’ STO
'''END'''
depth DUPN depth →LIST
steps "Token " token →STR + " → " + ROT →STR +
+ ‘steps’ STO
'''NEXT''' steps
≫ ≫ '<span style="color:blue">CALC</span>' STO
"3 4 2 * 1 5 - 2 3 ^ ^ / +" <span style="color:blue">CALC</span>
{{out}}
<pre>
2: 3.00012207031
1: { "Token 3 → { 3 }"
"Token 4 → { 3 4 }"
"Token 2 → { 3 4 2 }"
"Token * → { 3 8 }"
"Token 1 → { 3 8 1 }"
"Token 5 → { 3 8 1 5 }"
"Token - → { 3 8 -4 }"
"Token 2 → { 3 8 -4 2 }"
"Token 3 → { 3 8 -4 2 3 }"
"Token ^ → { 3 8 -4 8 }"
"Token ^ → { 3 8 65536 }"
"Token / → { 3 1.220703125E-04 }"
"Token + → { 3.00012207031 }" }
</pre>
Additional spaces and CR characters have been added to the above output to enhance readability.
=={{header|Ruby}}==
Line 6,014 ⟶ 6,308:
{{trans|Kotlin}}
{{libheader|Wren-seq}}
<syntaxhighlight lang="
var rpnCalculate = Fn.new { |expr|
| |||