Implement expression evaluation with static stack data structure
First, the topic:
When the user enters a legal expression, it can return the correct result. Operators that can be calculated include: plus, minus, multiply, divided, parentheses; the number of capabilities that can be calculated is within a real estimate. An error prompt is given for an abnormal expression. (Requires the use of a static stack data structure.)
Second, the data structure:
Data objects: d = {ai | ai∈elex, i = 1, 2, 3, ..., n, n ≥0}
Data relationship: r = {
The agreement A1 is the bottom of the stack, and an AN is the top of the stack.
Basic operation:
Push (& S, E)
Initial condition: The stack S already exists.
Operation Result: Insert Element E For New Stack Top Elements POP (& S, & E)
Initial conditions: The stack s already exists and is not empty.
Operation result: Delete the top of the stack of s and returns its value with E
.
.
.
Third, storage structure:
Typedef struct {
Array [N-1]
......
Array [0]
TOP
......
Int top;
Double array [n];
} Numstack; // Stack of real numbers
Typedef struct {
Int top;
Char array [n];
} OPSTACK; / / Stack of operators
Fourth, the main algorithm: (pseudo code)
#define n 50 # Define OK 1
#define error 0
#include
#include
Typedef struct {
Int top;
Double array [n];
Numstack;
Typedef struct {
Int top;
Char array [n];
} Opstack;
// Convert characters to the corresponding integer
INT CINT (CHAR MyCha) {
Return (MyChar-48);
}
// Digitally put the function
Status Pushnum (Numstack & Numstack, Double Num) {
IF (Numstack.top {Numstack.top ; Numstack.Array [Numstack.top-1] = NUM; RETURN OK; } Else Return Error; } // Digital Function Function Status PopNum (Numstack & Numstack, Double & Num) { IF (Numstack.top> 0) { Num = Numstack.Array [numStack.top-1]; Numstack.top -; Return OK; } Else Return Error; } // Operation of functions in the stack Status Pushop (Opstack & Opstack, Char & OP) { IF (OPSTACK.TOP OPSTACK.TOP ; Opstack.Array [OPSTACK.TOP-1] = OP; RETURN OK; } Else Return Error; } // Operating the function of the stack Status Popop (Opstack & Opstack, Char & OP) { IF (OPSTACK.TOP> 0) { Op = OPSTACK.Array [OPSTACK.TOP-1]; Opstack.top -; Return OK; } Else Return Error;} // Function for calculation Double Calc (Double A, Double B, CHAR C) { Double Result; Switch (c) { Case ' ': Result = a b; Break; Case '-': Result = a-b; break; Case '*': Result = a * b; Break; Case '/': result = a / b; Break; } Return Result; } / / Judgment the function of priority Char priority (char y, char x) { Char priority = '<'; Switch (x) { Case ' ': Case '-': if (Y == '(' || y == '#') priority = '>'; Break; Case '*': Case '/': IF (Y == '(' || y == '#' || y == ' ' || y == '-') priority = '>'; Break; Case '(': priority = '"; Case ')': if (y == '(') priority = '='; Break; Case '#': IF (y == '#') priority = '='; Break; DEFAULT: priority = 'e'; } Return priority; } / / Treatment of the body function of the expression Void Process (Numstack & Numstack, Opstack & Opstack, Char X) { Double A, B; CHAR C; Static Double Tempnum = 0.00000000; Static Int Len = 10; Static Int Dot = 0, FLAGS = 0; IF (isdigit (x) || x == '.') { IF (x == '.') DOT = 1; Else { IF (DOT == 0) Tempnum = Tempnum * 10 CINT (X); Else { Tempnum = Tempnum (double) CINT (X) / LEN; Len * = 10; } } } Else { IF (Flags == 0 &&x! = '(') {Pushnum (Numstack, Tempnum); tempnum = 0.00000000; LEN = 10; DOT = 0;} Switch (priority (opstack.Array [OPSTACK.TOP-1], X)) { Case '>': Pushop (Opstack, X); Flags = 0; Break; Case '<': POPOP (Opstack, & C); PopNum (Numstack, & B); PopNum (Numstack, & A); Pushnum (Numstack, Calc (A, B, C)); FLAGS = 1; Process (Numstack, Opstack, X); Break; Case '=': POPOP (Opstack, & C); Flags = 1; Break; Default: Printf ("WRONG Express!"); exit (0); } } } // main function MAIN () { Numstack Numstack; Opstack Opstack; Char * S; INT i = 0; Numstack.top = 0; OPSTACK.TOP = 0; Pushop (& Opstack, '#'); Printf ("/ NENTER YOUR EXPRESSION ADN End It with #:"); scanf ("% s", s); For (i = 0; i Process (& Numstack, & Opstack, S [i]); Printf ("THE RESULT IS% F", Numstack.Array [Numstack.top-1]); } V. Test data: Ignore ....6, small knot: This experiment is difficult, I have made several versions. The initial version is due to only one stack, causing a few decisions. The second version is used to input once, and cannot handle parentheses. This version, I personally be more satisfied. The code is only 92 lines, but the function is perfect, can handle the addition and subtraction of the real number, the multi-bracing method has no error, and can perform multi-parent-brackets. And there is a certain identification ability for the wrong expression. Source code for C language: #define n 50 #include #include Typedef struct { Int top; Double array [n]; Numstack; Typedef struct { Int top; Char array [n]; } Opstack; INT CINT (CHAR MyCha) { Return (MyChar-48); } Void Pushnum (Numstack * Numstack, Double Num) { Numstack-> TOP ; Numstack-> Array [Numstack-> TOP-1] = NUM; } Void PopNum (Numstack * Numstack, Double * Num) { * Num = Numstack-> Array [Numstack-> TOP-1]; Numstack-> TOP -; } Void Pushop (OPSTACK * OPSTACK, CHAR OP) { Opstack-> TOP ; Opstack-> array [opstack-> TOP-1] = OP; } Void Popop (Opstack * Opstack, Char * OP) { * OP = OPSTACK-> Array [opstack-> TOP-1]; Opstack-> TOP -; } Double Calc (Double A, Double B, CHAR C) { Double Result; Switch (c) { Case ' ': Result = a b; Break; Case '-': Result = a-b; break; Case '*': result = a * b; break; case '/': result = a / b; break; } Return Result; } Char priority (char y, char x) { Char priority = '<'; Switch (x) { Case ' ': Case '-': if (Y == '(' || y == '#') priority = '>'; Break; Case '*': Case '/': IF (Y == '(' || y == '#' || y == ' ' || y == '-') priority = '>'; Break; Case '(': priority = '"; Case ')': if (y == '(') priority = '='; Break; Case '#': IF (y == '#') priority = '='; Break; DEFAULT: priority = 'e'; } Return priority; } Void Process (Numstack * Numstack, Opstack * Opstack, Char X) { Double A, B; CHAR C; Static Double Tempnum = 0.00000000; Static Int Len = 10; Static Int Dot = 0, FLAGS = 0; IF (isdigit (x) || x == '.') { IF (x == '.') DOT = 1; Else { IF (DOT == 0) Tempnum = Tempnum * 10 CINT (X); Else { Tempnum = Tempnum (double) CINT (X) / LEN; Len * = 10; } } } Else { IF (Flags == 0 &&x! = '(') {Pushnum (Numstack, Tempnum); tempnum = 0.00000000; LEN = 10; DOT = 0;} Switch (priority (opstack-> array [opstack-> TOP-1], x)) { Case '>': Pushop (Opstack, X); Flags = 0; Break; Case '<': POPOP (Opstack, & C); PopNum (Numstack, & B); PopNum (Numstack, & A); Pushnum (Numstack, Calc (A, B, C)); FLAGS = 1; PROCESS (Numstack, Opstack, X); Break; Case '=': POPOP (Opstack, & C); Flags = 1; Break; Default: Printf ("WRONG Express!"); exit (0); } } } MAIN () { Numstack Numstack; OpStack Opstack; Char S [N]; INT i = 0; Numstack.top = 0; OPSTACK.TOP = 0; Pushop (& Opstack, '#'); Printf ("/ NENTER YOUR EXPRESSION AND End IT with #:"); scanf ("% s", s); For (i = 0; i Process (& Numstack, & Opstack, S [i]); Printf ("THE RESULT IS% F", Numstack.Array [Numstack.top-1]); }
