/* Inspired from https://www.includehelp.com/c/infix-to-postfix-conversion-using-stack-with-c-program.aspx This program converts infix expression to postfix expression. NOTE: "Tor" used in an identifier means "related to operaTOR, "Rand" when "related to opeRAND. A record type nammed opTorRand_t that can contain information on an operator or an operand is defined. The field _prec countains the precedence of the operator (IN[1..11]), or 0 if the rec is related to an operand. The field _txt is a string that is mainly used for degugging pur- pose. A field nammed _value contains either the numérical value of an operand or the ordinal of the operator. The web page mentionned above describes clearly the way this software works, but without considering the facts that one or more unary operands can be introduced in front of an operand, or a '('. That point is a probleme considering that there are characters common to unary an binary operators (+, -, < and >). This point had been simply treated considering that while scanning the infix expression string, we always know if we are especting an operator or an operand. While waiting for an operand, only binary operands and ')' are accepted, oterwise, operand and '(' that MAY BE preceded by unary operators are accepted. Unary operators : There precedence is equale to 1. Tey are logical-not: "!" bitwise not: "~" unary plus: "+" unary minus: "-" Most significant byte: "<" Less significant byte: ">" The character '<' means that the value of the following operand will be reduced to its most significant byte; it is equivalent to v ← v>>8. The '>' is simlar but the least significant byte is used, then it is equivalent to v ← v&0xFF. The use of unary operators has been restric- ted so: - only one of '+' and '-' characters is accepted, - only one of '<' and '>' characters is accepted but when no '!' is used, - only one '~' character is acepted but when no '!' is used, - the character '!' is not accepted more than two times, but without any '<', '>' or '!'. These restrictions permit the unary operators used for a operand to be storable in a single seven bits variable. If relevant, it is stored in the _compU field of an operand record. It can be stored in the _compU field of an operator record if it concerns an operand being a parenthesized expression. NOTE that at the moment of evaluating an operand preceded by unary operator(s), the precedence is fixed: the order of evaluation is '!'s first then '~', then '+' or '-' then '<' or '>'. Binary operators : Tockens precedences - "*" multiplication, "/" division, "%" modulus : 2 - "+" addition, "-" subtraction : 3 - "<<" bitwise shift left, ">>" right, ">>>" unsigned /2 : 4 - "<" relational LT, "<=" LT, "> GT, ">=" GE : 5 - "=" equality EQ, "==" EQ, "!=" NE, "<>" NE : 6 - "&" bitwise-and : 7 - "^" bitwise-xor (EOR) : 8 - "|" bitwise-or : 9 - "&&" logical-and : 10 - "||" logical-or : 11 See bellow for a clearer table. NOTE that the lower the number, the higher the precedence. I hope that the reader is used to the notion of precedence. Adding A to B and C to D then adding the results should be entered so: "(A+B)*(C+D)" the only flexibility is that you may write it so:"(C+D)*(A+B)". But this "(A*B)+(C*D)" may be written so: "A*B+C*D" because the precedence of the multiplication is higher than the one of the addition. There is no simplifi- cation of that: (A&15)==(B&15) are the 4 least significant bits of 'A' equale to those of 'B'. cd ~/_4/2_emu_6301/as6303/ ; gcc $C8_DEV -Werror -g src/Evaluate_in.c && $VAL8 './a.out A+(B*C-(D/E)*G)*H' *//** cd ~/_4/2_emu_6301/as6303/ ; gcc $C8_DEV -Werror -g src/Evaluate_in.c && $VAL8 ./a.out '-A+(-B*-C-(-D/-E)*-G)*-H' cd ~/_4/2_emu_6301/as6303/ ; gcc $C8_DEV -Werror -g src/Evaluate_in.c && $VAL8 ./a.out '!A+(!B*!C-(!D/!E)*!G)*!H' */ /// NOTE Uncomment the following line to see details while infix expression developement // #define DEVEL_INFIX /// NOTE Uncomment the following line to see more details while infix expression developement // #define DEBUGTORSTACK /// NOTE Uncomment the following line to see details while parenthesized expression devel. #define DEVEL_PARENTHESIZED #include #include #include // For at least [int8_t..int64_t] &[uint8_t..uint64_t] #include // For at least exit() #include // For at least isdigit(char) #include "src/Vt-200.color.h" // Screen coloring #define SIZE 100 /* Related to the maximum acceptable operators / operands */ #define UOPTOR_CHRS "!~+-<>" /* Allowed char in anary only operators */ #define OPTOR_CHARS "()!~+-<>*/%<>=&^|" /* Allowed char in any operator */ #define BOPTOR_CHARS ")-+*/%<>=&^|" /* Not allowed char after Rand beginning with '0' */ // The following two lines are to easy the development with Nemiver int Main (int argc, char *argv[]); int main (int argc, char *argv[]) { Main(argc, argv); } typedef struct dynStr_t { char *_DyStr; // String of char stored in (re-)allocated memory size_t _DyStrMemSiz // Size of (last) memory (re-)allocation ,_DyStrLen; // Exact equivalent to strlen(_DyStr) } dynStr_t; typedef struct { /// Operand or operator container uint32_t _value; // Value of operand or order of operator union { dynStr_t _dText; // Identifier string NOTE used in this source file char _opTorT[32]; // Operand string } _txt; uint8_t _prec // 0 for operand, Precedence (IN[1..11]) for operand ,_compU; // Unary operator(s) appalyable. 0 -> no unary operator // If != 0 for an Operand, to be applyed on it's value // If != 0 for an Operator, to be applyed on result of the operation } opTorRand_t; enum { /* +------------------------------------ _prec : precedence | +-------------- _value : Indice | | +---------- _txt : Tocken char / string | | | +---- _opTorT : Tocken string length | | | | */ /* +---+----------------+----+-----+---+ */ /* |99 | Parentese | -1 | (…) | 1 | WARNING -1 could provoke a bus error */ /* +---+----------------+----+-----+---+ */ /* | 1 | logical-not | 0 | !… | 1 | */ kLogNot // 0: 1 "!" /* | | bitwise not | 1 | ~… | 1 | */ ,kBitNot // 1: 1 "~" /* | | unary + | 2 | +… | 1 | */ ,kUnarPlu // 2: 1 "+" /* | | unary negation | 3 | -… | 1 | */ ,kUnarNeg // 3: 1 "-" /* | | MsByte | 4 | <… | 1 | */ ,kMsByte // 4: 1 "<" /* | | LsByte | 5 | >… | 1 | */ ,kLsByte // 5: 1 ">" /* +---+----------------+----+-----+---+ */ /* | 2 | multiplication | 6 | * | 1 | */ ,kMul // 6: 2 "*" /* | | division | 7 | / | 1 | */ ,kDiv // 7: 2 "/" /* | | modulus | 8 | % | 1 | */ ,kModulo // 8: 2 "%" /* +---+----------------+----+-----+---+ */ /* | 3 | addition | 9 | + | 1 | */ ,kAdd // 9: 3 "+" /* | | subtraction | 10 | - | 1 | */ ,kSub // 10: 3 "-" /* +---+----------------+----+-----+---+ */ /* | 4 | bitwise shift | 11 | << | 2 | */ ,kBitLsl // 11: 4 "<<" /* | | | 12 | >> | 2 | */ ,kBitLsr // 12: 4 ">>" /* | | | 13 | >>> | 3 | */ ,kBitAsr // 13: 4 ">>>" /* +---+----------------+----+-----+---+ */ /* | 5 | relational | 14 | < | 1 | */ ,kRelLT // 14: 5 "<" /* | | | 15 | <= | 2 | */ ,kRelLE // 15: 5 "<=" /* | | | 16 | > | 1 | */ ,kRelGT // 16: 5 ">" /* | | | 17 | >= | 2 | */ ,kRelGE // 17: 5 ">=" /* +---+----------------+----+-----+---+ */ /* | 6 | equality | 18 | = | 2 | */ ,kCompEQ // 18: 6 "=" /* | | | 18 | == | 1 | ,kCompEQ // 18: 6 "==" */ /* | | | 19 | != | 2 | */ ,kCompNE // 19: 6 "!=" /* | | | 19 | <> | 2 | ,kCompNE // 19: 6 "<>" */ /* +---+----------------+----+-----+---+ */ /* | 7 | bitwise-and | 20 | & | 1 | */ ,kBitAnd // 20: 7 "&" /* +---+----------------+----+-----+---+ */ /* | 8 | bitwise-xor | 21 | ^ | 1 | */ ,kBitXOr // 21: 8 "^" /* +---+----------------+----+-----+---+ */ /* | 9 | bitwise-or | 22 | | | 1 | */ ,kBitOr // 22: 9 "|" /* +---+----------------+----+-----+---+ */ /* |10 | logical-and | 23 | && | 2 | */ ,kLogAnd // 23:10 "&&" /* +---+----------------+----+-----+---+ */ /* |11 | logical-or | 24 | || | 2 | */ ,kLogOr // 24:11 "||" /* +---+----------------+----+-----+---+ */ }; /* { "!", "~", "+", "-", "<", ">", "*", "/", "%", "+", "-","<<",">>",">>>","<","<=", ">",">=", "=","<>", "&", "^", "|", "&&", "||"} */ const uint8_t kPreced[] = { 1, 1, 1, 1, 1, 1, 2, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, 5, 6, 6, 7, 8, 9, 10, 11 }; const uint8_t kTockLen[] = { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 3, 1, 2, 1, 2, 1, 2, 1, 1, 1, 2, 2 }; /// Declarations related to the unary operators enum UniBit_t { LogNot1 = 0x40 /* +--------- kLogNotB1: '!' */ ,LogNot2 = 0x20 /* |+-------- kLogNotB2: '!' */ ,BitNot = 0x10 /* ||+------- kBitNotB: '~' */ ,UnarPlu = 0x08 /* |||+------ kUnarPluB: '+' */ ,UnarNeg = 0x04 /* ||||+----- kUnarNegB: '-' */ ,MsByte = 0x02 /* |||||+---- kMsByteB: '<' */ ,LsByte = 0x01 /* ||||||+--- kLsByteB: '>' */ }; /* ||||||| */ /* -xxxxxxx uniFlags */ /// Declarations related to errors const char *kErrMess[] = { /* kErr_NoErr */ "!!!! No error !!!!"/* kErr_MissMem */ ,"Missing memory"/* kErr_StkOver */ ,"Stack overflow"/* kErr_StkUnder */ ,"Expression too complicated"/* kExp_Over */ ,"Expression error"/* kExp_MuchUni */ ,"Too many successive unary operators"/* kExp_OpOrUni */, "Operand, Unary operator or '(' was expected"/* kExp_BinOpReq */, "Binary operator or ')' was expected"/* kExp_MisParClo */, "Missing ')'"/* kExp_UnSyntax */, "Unary operator syntax"/* kExp_NoDecSntx */, "Non decimal character encountered"/*/* kExp_NoHexSntx */, "Non hexadecimal character encountered"/* kExp_NoBinSntx */, "Non binary character encountered"/* kExp_NoOctSntx */, "Non octal character encountered"/* kExp_RandTooLg */, "Numeric operand is too long" /* kExp_InvalBas */, "Base not specified (x,X,d,D,o,O,b or B)"/* kExp_PadTrunc */, "Operand truncated (to fit 16 bits)" /* Warning kExp_DivBy0 */, "Division by 0" /* Warning */ }; typedef enum { kErr_NoErr = 0 ,kErr_MissMem ,kErr_StkOver // See Eval_PushTor() & Eval_PushExp() ,kErr_StkUnder // See Eval_PopTor() & Eval_PopExp() ,kExp_Over // See Eval_PostAdd() ,kExp_MuchUni // Unary stack overflow ,kExp_OpOrUni // See Eval_Infix2Postfix() ,kExp_BinOpReq // See Eval_CloPar() ,kExp_MisParClo // See Eval_Infix2Postfix() ,kExp_UnSyntax // see locHandelUnaTor() ,kExp_NoDecSntx // See Eval_IsOperand() ,kExp_NoHexSntx // See Eval_IsOperand() ,kExp_NoBinSntx // See Eval_IsOperand() ,kExp_NoOctSntx // See Eval_IsOperand() ,kExp_RandTooLg // See Eval_IsOperand() ,kExp_InvalBas // See Eval_IsOperand() ,kExp_PadTrunc // See Eval_IsOperand() Warning ,kExp_DivBy0 // See Eval_EvalEpression Warning } errVal_t; /// Globals // These variables must be globals for access from the debugging functions opTorRand_t gTorsStk[SIZE] // Binary operators stack ,gOutOpStk[SIZE]; // Unary operators stack int gTorStkLen = 0 // Size of binary operators stack ,gOutOpStkLn = 0; // Size of unary operators stack void Eval_ExitErr (errVal_t err) { /// ************************************************************************** // Handels printing in case of an (fatal) error printf(_Ro("%s")"\nAbandon: ", kErrMess[err]); exit(EXIT_FAILURE); } void Xas_AsmWarn (errVal_t err) { /// ************************************************************************** // Handels printing in case of a (simple) warning char *strP; int r = asprintf(&strP, _Ro("\nWarning: ")"%s", kErrMess[err]); if (r < 0) Eval_ExitErr(kErr_MissMem); fprintf(stderr, "%s\n", strP); } char *Eval_DebugUniPrint (uint8_t uPack, char uP[8]) { /// ************************************************************************** // Simply adjust "uP" string figure out the set of unary operators "pack" *uP = 0; strcat(uP, uPack & 0x40 ? "!" : ""); strcat(uP, uPack & 0x20 ? "!" : ""); strcat(uP, uPack & 0x10 ? "~" : ""); strcat(uP, uPack & 0x08 ? "+" : ""); strcat(uP, uPack & 0x04 ? "-" : ""); strcat(uP, uPack & 0x02 ? "<" : ""); strcat(uP, uPack & 0x01 ? ">" : ""); return uP; } void Eval_DebugOpPrint (opTorRand_t *oper) { /// ************************************************************************** // Displays some details of an operator or an operand "oper" is pointing to char uP[8]; if (oper->_prec) { // Operator (ie: -<) printf(_Ro("%s") _ri, oper->_txt._opTorT); printf ("%s", Eval_DebugUniPrint(oper->_compU, uP)); printf(C_" "); } else { // Operand (ie: -D or -D(0044)) printf(_ri); printf ("%s", Eval_DebugUniPrint(oper->_compU, uP)); printf(C_ _Ja("%s")"(" _Gr("%04X")") ", oper->_txt._opTorT, oper->_value); // printf(C_ _Ja("%s")" ", oper->_txt._opTorT); } } void Eval_DebugPostPrint (int line) { /// ************************************************************************** // Print the (final) postfix expression with unary operators int i; if (line) printf(" [" _Ro("%d")"]: gOutOpStkLn: %d ---> ", line, gOutOpStkLn); for (i = 0; i < gOutOpStkLn; i++) Eval_DebugOpPrint(&gOutOpStk[i]); printf("\n"); } #ifndef DEBUGTORSTACK #define Eval_DebugTorStackPrint(l) ; #else void Eval_DebugTorStackPrint (int line) { /// ************************************************************************** // Print the binary operators stack content for debugging int i; printf(" [" _Ma("%d")"]: ", line); for (i = 0; i < gTorStkLen; i++) { printf(_Ja("%s")"%d ", gTorsStk[i]._txt._opTorT, gTorsStk[i]._prec); } printf("\n"); } #endif int Eval_IsOperand (char **idx, opTorRand_t *oper) { /// ************************************************************************** // Check if an operand is pointed to by *idx. Returns != 0 if true and moves *idx to point the // character immediately following this operand, otherwise, returns 0 and *idx is unchanged. // WARNING * -> PC uint32_t v = 0; char *ref = *idx // To compute the length of the tocken ,*cPtr = oper->_txt._opTorT // Where to put the read tocken ,*tcPtr; // Position of the base indicator const char *bases = "xdobXDOB"; // To check the base indicator if (!**idx) return 0; oper->_prec = 0; // If returns !0, means operand encountered switch (**idx) { case 0: // nil (end of C string) return 0; /// Numerical values case '0': // Either 0, 0xxx, or 0bxxx *idx += 1; if (!(tcPtr = strchr(bases, **idx))) { // Not followed by a base specifier character if (!strchr(BOPTOR_CHARS, **idx)) // Not followed by an binary operator or ')' Eval_ExitErr(kExp_InvalBas); goto EnterDec; // Enter decimal number } *idx += 1; // Skip the base specifier switch ((tcPtr - bases) & 3) { case 0: goto EnterHexa; case 1: if (!isdigit(**idx)) // At least one decimal character should follow Eval_ExitErr(kExp_NoDecSntx); goto EnterDec; case 2: goto EnterOct; case 3: goto EnterBin; } case '$': // Hexadecimal based number follows *idx += 1; // Skip base indicator if (!isxdigit(**idx)) // At least one hexadecimal character should follow Eval_ExitErr(kExp_NoHexSntx); EnterHexa: for (; isxdigit(**idx); *idx += 1) v = (v << 4) | ((**idx & 0xF) + (isdigit(**idx) ? 0 : 9)); goto FinishNum; case '%': // Binary based number follows *idx += 1; // Skip base indicator if (**idx != '0' && **idx != '1') // At least one binary character should follow Eval_ExitErr(kExp_NoBinSntx); EnterBin: for (; **idx == '0' || **idx == '1'; *idx += 1) v = (v << 1) | (**idx & 1); goto FinishNum; case '@': // Octal based number follows *idx += 1; // Skip if (**idx < '0' || **idx > '7') // At least one octal character should follow Eval_ExitErr(kExp_NoOctSntx); EnterOct: for (; **idx >= '0' && **idx <= '7'; *idx += 1) v = (v << 3) | (**idx & 7); goto FinishNum; default: if (isdigit(**idx)) { EnterDec: for (; isdigit(**idx); *idx += 1) v = (v * 10) + (**idx & 0xF); FinishNum: if (v & ~0xFFFF) // Result necessite Limitation to 16 bits Xas_AsmWarn(kExp_PadTrunc); // Warning oper->_value = v &0xFFFF; // Check if we have space to store the entier incoming operand string if ((size_t)(*idx - ref) >= (sizeof(oper->_txt._opTorT) - 1)) Eval_ExitErr(kExp_RandTooLg); while (ref != *idx) // Copys operand *cPtr++ = *ref++; *cPtr = 0; // Ends C string return 1; // Got an operand } /// Symboles, identifiers and others else if (isalpha(**idx)) { // This part could use opTorRand_t._dText as a dynStr_t oper->_value = (int)**idx; // ASCII value, while developping oper->_txt._opTorT[0] = **idx; oper->_txt._opTorT[1] = 0; // Ends C string *idx += 1; // Skip "used" characters return 1; // Got an operand } else return 0; } } int Eval_IsOperator (char **idx, opTorRand_t *oper, int U_nonU) { /// ************************************************************************** // Determine whether an operator is pointed to by *idx. The "U_nonU" parameter fixes if the // operator must be an unary one if != 0, or a binary one if 0. Returns 0 and *idx is // unchanged *idx was not pointing an operator of the type specified (by "U_nonU"), otherwise // returns precedence of the operator and *idx is moved to point the character immediately // following this operator. If an operator is found, the fields of the pointed operator "oper" // are set corresponding to it. char c1 = *(*idx + 1) ,c2 = *(*idx + 2); int8_t xtra = 0 // For dual length operand (= or ==) ,i, lim; int loc_Set (int8_t val) { /// ----------------------------------------------- // Sets the *oper fields to complete information related to the found unary operator. Written // so to esay tyhe writing (-: and hoping the reading) oper->_prec = kPreced[oper->_value = val]; for (i = 0, lim = kTockLen[val] + xtra; i < lim; *idx += 1, i++) oper->_txt._opTorT[i] = **idx; oper->_txt._opTorT[i] = 0; // Ends C string return 1; } /// ------------------------------------------------------------------------ if (!**idx) return 0; memset(oper, 0, sizeof(opTorRand_t)); // oper->_dText = EMPTY_DYNSTR; if (U_nonU) switch (**idx) { /// Unary - case '!': // kLogNot "!" return loc_Set(kLogNot); case '~': // kBitNot "~" return loc_Set(kBitNot); case '+': // kUnarPlu "+" return loc_Set(kUnarPlu); case '-': // kUnarNeg "-" return loc_Set(kUnarNeg); case '<': // kMsByte "<" return loc_Set(kMsByte); case '>': // kLsByte ">" return loc_Set(kLsByte); default: return 0; } else switch (**idx) { /// Others - case '!': // kCompNE "!=" if (c1 == '=') return loc_Set(kCompNE); case '+': // kAdd "+" return loc_Set(kAdd); case '-': // kSub "-" return loc_Set(kSub); case '*': // kMul "*" WARNING PC return loc_Set(kMul); case '/': // kDiv "/" return loc_Set(kDiv); case '%': // kModulo "%" return loc_Set(kModulo); case '<': // kRelLT "<" // kBitLsl "<<" // kRelLE "<=" // kCompNE "<>" NOTE or "!=" if (c1 == '<') return loc_Set(kBitLsl); // << else if (c1 == '>') return loc_Set(kCompNE); // <> else if (c1 == '=') return loc_Set(kRelLE); // <= else return loc_Set(kRelLT); // < case '>': // kRelGT ">" // kBitLsr ">>" // kRelGE ">=" // kBitAsr ">>>" if (c1 == '>') { // >> if (c2 == '>') // >>> return loc_Set(kBitAsr); // >>> else return loc_Set(kBitLsr); // >> } else if (c1 == '=') return loc_Set(kRelGE); // >= else return loc_Set(kRelGT); // > case '=': // kCompEQ "=" NOTE or "==" if (c1 == '=') xtra = 1; return loc_Set(kCompEQ); case '&': // kBitAnd "&" // kLogAnd "&&" if (c1 == '&') return loc_Set(kLogAnd); // && else return loc_Set(kBitAnd); // & case '^': // kBitXOr "^" return loc_Set(kBitXOr); case '|': // kBitOr "|" // kLogOr "||" if (c1 == '|') // || return loc_Set(kLogOr); else return loc_Set(kBitOr); } return 0; } uint16_t Eval_EvalOperand (uint8_t compU, uint32_t value) { /// ************************************************************************** // Evaluate the value of an operand considering the preceding unary operator. NOTE that the // precedence is fixed : '!'s first then '~', then '+' or '-' then '<' or '>' int tv = value; if (compU & LogNot1) // kLogNot '!' tv = !tv; if (compU & LogNot2) // kLogNot '!' tv = !tv; if (compU & BitNot ) // kBitNot '~' tv = ~tv; /* if (compU & UnarPlu) // kUnarPlu '+' ;*/ if (compU & UnarNeg) // kUnarNeg '-' tv = -tv; if (compU & MsByte ) // kMsByte '<' tv = (tv & 0xFF00) >> 8; if (compU & LsByte ) // kLsByte '>' tv = tv & 0xFF; return (tv & 0xFFFF); } uint16_t Eval_EvalEpression (uint16_t v1, int opOrd, uint16_t v2) { /// ************************************************************************** // Evaluates the expression "v1" "opOrd" "v2" (ie "A * B", or "%101 +$1200") if (opOrd == kBitLsr) { while (v2 && v1) v1 = (int16_t)v1 / 2; return v1; } else if (opOrd == kDiv && !v2) Xas_AsmWarn(kExp_DivBy0); else switch (opOrd) { case kMul :return (int16_t)v1 * (int16_t)v2; case kDiv :return (int16_t)v1 / (int16_t)v2; case kModulo :return (int16_t)v1 % (int16_t)v2; case kAdd :return (int16_t)v1 + (int16_t)v2; case kSub :return (int16_t)v1 - (int16_t)v2; case kBitLsl :return v1 << v2; case kBitAsr :return v1 >> v2; case kRelLT :return !!((int16_t)v1 < (int16_t)v2); case kRelLE :return !!((int16_t)v1 <= (int16_t)v2); case kRelGT :return !!((int16_t)v1 > (int16_t)v2); case kRelGE :return !!((int16_t)v1 >= (int16_t)v2); case kCompEQ :return v1 == v2; case kCompNE :return v1 != v2; case kBitAnd :return v1 & v2; case kBitXOr :return v1 ^ v2; case kBitOr :return v1 | v2; case kLogAnd :return v1 && v2; case kLogOr :return v1 || v2; } return 0; } void Eval_Infix2Postfix (char infix_exp[]) { /// ************************************************************************** /// Declarations related to the unary operators #define CLR_UFLAGS (uniFlags = 0) #define SETLOGNOT1 (uniFlags |= LogNot1) #define SETLOGNOT2 (uniFlags |= LogNot2) #define SETBITNOT (uniFlags |= BitNot ) #define SETUNARPLU (uniFlags |= UnarPlu) #define SETUNARNEG (uniFlags |= UnarNeg) #define SETMSBYTE (uniFlags |= MsByte ) #define SETLSBYTE (uniFlags |= LsByte ) #define ISLOGNOT1 (uniFlags & LogNot1) #define ISLOGNOT2 (uniFlags & LogNot2) #define ISBITNOT (uniFlags & BitNot ) #define ISUNARPLU (uniFlags & UnarPlu) #define ISUNARNEG (uniFlags & UnarNeg) #define ISMSBYTE (uniFlags & MsByte ) #define ISLSBYTE (uniFlags & LsByte ) opTorRand_t locOpe ,lOpe2 ,missed /// 2019-06-14 ,*lstAdded; uint8_t lPrec ,uniFlags = 0 // Unary operators set ,Rand_Tor = 1 // 1 -> Operand requested, 0 -> Operator requested ,uFlgsStk[SIZE]; // Unary operator stack int uFlgStkT = 0; // Unary operator stack pointer char *inSPtr = infix_exp ,**idx = &inSPtr; void Eval_PushTor (opTorRand_t *opTor) { /// ---------------------------------- // Push a non unary operator on stack if (gTorStkLen >= (SIZE - 1)) Eval_ExitErr(kErr_StkOver); // "Stack overflow." Never come back routine gTorsStk[gTorStkLen++] = *opTor; } opTorRand_t *Eval_PopTor (void) { /// ----------------------------------------- // Pop an operator if (gTorStkLen <= 0) Eval_ExitErr(kErr_StkUnder); // "Expression too complicated" Never come back routine return &gTorsStk[--gTorStkLen]; } void Eval_PushUniFlags (void) { /// ------------------------------------------ // Push a non unary operator on stack if(uFlgStkT >= SIZE) Eval_ExitErr(kExp_MuchUni); // "Too many successive unary operators" Never come back uFlgsStk[++uFlgStkT] = uniFlags; uniFlags = 0; } uint8_t Eval_PopUniFlags (void) { /// ---------------------------------------- // Pop an operator uniFlags = uFlgStkT < 0 ? 0 : uFlgsStk[uFlgStkT--]; return uniFlags; } void locHandelUnaTor (void) { /// -------------------------------------------- uniFlags = 0; while (Eval_IsOperator(idx, &locOpe, 1)) { // Get unary operators only switch (locOpe._value) { // Build uniFlags function of locOpe._prec case 0: // '!' Count & keep until 2, syntax error if more if (ISMSBYTE || ISLSBYTE || (ISLOGNOT1 && ISLOGNOT2)) Exp_UnSyntaxL: Eval_ExitErr(kExp_UnSyntax); // "Unary operator syntax" if (!ISLOGNOT1) SETLOGNOT1; else SETLOGNOT2; break; case 1: // '~' syntax error if more if more than 1 if (ISBITNOT) goto Exp_UnSyntaxL; SETBITNOT; break; case 2: // '+' syntax error if more than 1 if (ISUNARNEG || ISUNARPLU) goto Exp_UnSyntaxL; SETUNARPLU; break; case 3: // '-' syntax error if more than 1 if (ISUNARNEG || ISUNARPLU) goto Exp_UnSyntaxL; SETUNARNEG; break; case 4: // '<' syntax error if more than 1 or kLsByte too if (ISMSBYTE || ISLSBYTE || ISLOGNOT1 || ISLOGNOT2) goto Exp_UnSyntaxL; SETMSBYTE; break; case 5: // '>' syntax error if more than 1 or kMsByte too if (ISMSBYTE || ISLSBYTE || ISLOGNOT1 || ISLOGNOT2) goto Exp_UnSyntaxL; SETLSBYTE; } } } void Eval_PostAdd (opTorRand_t *opTor) { /// --------------------------------- if (gOutOpStkLn >= (SIZE - 1)) // This should never append Eval_ExitErr(kExp_Over); // "Expression error" Never come back routine lstAdded = &gOutOpStk[gOutOpStkLn]; // Keep track of the last added gOutOpStk[gOutOpStkLn++] = *opTor; // Done } void Eval_CloPar (void) { /// ------------------------------------------------ // '(' encountered or end of infix string if (Rand_Tor) // Error if operand is espected Eval_ExitErr(kExp_BinOpReq); // "Operand or Unary operator was expected" lOpe2 = *Eval_PopTor(); // pop and keep popping until while(lOpe2._prec != 99) { // '(' encounterd */ Eval_PostAdd(&lOpe2); // so pop all higher precendence operator and lOpe2 = *Eval_PopTor(); } if (gOutOpStkLn > 2) /// 2019-06-14 lstAdded->_compU = Eval_PopUniFlags(); uniFlags = 0; } void Eval_OpenPar (opTorRand_t *locItem) { /// ------------------------------- // ')' encountered or no '(' at beginning of infix string locItem->_value = -1; // Prepare a "fake" inSPtr to push "(" like locItem->_prec = 99; locItem->_compU = uniFlags; /// Places eventual unary operator(s) locItem->_txt._opTorT[0] = '('; locItem->_txt._opTorT[1] = 0; // Ends C string Eval_PushTor(locItem); // Like push '(' onto stack Eval_PushUniFlags(); } void Eval_GetNxtChar (void) { /// -------------------------------------------- #ifdef DEVEL_INFIX printf("\n" _Ro("%c")"%s\n", *inSPtr, inSPtr + 1); Eval_DebugPostPrint(__LINE__); Eval_DebugTorStackPrint(__LINE__); #endif if (Rand_Tor // It's OK while waiting for Operand && strchr(UOPTOR_CHRS, *inSPtr)) // Handels case of [!…}](expression) locHandelUnaTor(); if (*inSPtr == '(') { /// If '(' pointed inSPtr++; if (!Rand_Tor) // Error if operator is espected Eval_ExitErr(kExp_BinOpReq); // "Binary operator or ')' was expected" Eval_OpenPar(&locOpe); // Handel eventual unary operator(s) } else if(*inSPtr == ')') { /// if ')' pointed inSPtr++; Eval_CloPar(); } else if (Rand_Tor) { /// Operand espected if (*inSPtr !='(') { if (!Eval_IsOperand(idx, &locOpe)) Eval_ExitErr(kExp_OpOrUni); // "Operand or Unary operator was expected" locOpe._compU = uniFlags; // Places eventual unary operator(s) Eval_PostAdd(&locOpe); // add operand to postfix expr uniFlags = 0; Rand_Tor = 0; // Operand needed, now } } else { /// Operator espected if (!Eval_IsOperator(idx, &locOpe, 0)) Eval_ExitErr(kExp_BinOpReq); // Never come back routine if (gTorStkLen > 0) { // If something in operators stack lPrec = locOpe._prec; lOpe2 = *Eval_PopTor(); // NOTE only Tor pushed ! (no lOpe2._prec > 1 test) while(lOpe2._prec <= lPrec) { // To pop all higher precendence operator and Eval_PostAdd(&lOpe2); // Add to postfix expression lOpe2 = *Eval_PopTor(); } Eval_PushTor(&lOpe2); // Put back the extra popped inSPtr Eval_PushTor(&locOpe); // Now, push current oprerator } else missed = locOpe; /// 2019-06-14 Rand_Tor = 1; // Operand needed, now } #ifdef DEVEL_INFIX printf("%s, " _Cy("%02X")" ", Rand_Tor ? _Ro("Rand"):_Ma("Tor"), uniFlags); Eval_DebugPostPrint(__LINE__); Eval_DebugTorStackPrint(__LINE__); #endif } /// ------------------------------------------------------------------------ while(*inSPtr) // run loop till end of infix expression Eval_GetNxtChar(); Eval_PostAdd(&missed); /// 2019-06-14 if (gTorStkLen != 0) // Only the first '(' should stay Eval_ExitErr(kExp_MisParClo); // Never come back routine locOpe._value = -1; // Terminate output } void Eval_Postfix2Parent (void) { /// ************************************************************************** // Back to parenthesized expression. This is occasion to compute the final value. typedef struct { /// Operand or operator container char *_string; // NOTE usefull only if DEVEL_PARENTHESIZED is defined uint32_t _value; // Value of operand or order of operator uint8_t _prec; // 1 for unic operand, Precedence (IN[2..11]) for expression } grpPar_t; char *strP // NOTE usefull only if DEVEL_PARENTHESIZED is defined ,*hStr // NOTE usefull only if DEVEL_PARENTHESIZED is defined ,uP[8]=""; // NOTE usefull only if DEVEL_PARENTHESIZED is defined grpPar_t expStk[SIZE] // Any type operators stack ,*exp1, *exp2; int expStkL = 0 // Pointer on top of operators stack ,r, ix; uint16_t realVal ,tVal; void Eval_PushExp (char *string, uint32_t value, uint8_t prec) { /// --------- // Push a non unary operator on stack if (expStkL >= (SIZE - 1)) Eval_ExitErr(kErr_StkOver); // "Stack overflow." Never come back routine expStk[expStkL]._string = string; expStk[expStkL]._value = value; expStk[expStkL++]._prec = prec; } grpPar_t *Eval_PopExp (void) { /// ------------------------------------------- // Pop an operator if (expStkL <= 0) Eval_ExitErr(kErr_StkUnder); // "Expression too complicated" Never come back routine return &expStk[--expStkL]; } /// ------------------------------------------------------------------------ /* 1 2 3 4 5 6 7 8 9 a b c d e stk A+(B*C-(D/E)*G)*H 0 _A _B _C *_ _D _E /_ _G *_ -_ _H *_ +_ 0 | | | | | | [a] 1 A | | | | | | [b] 1 B | | | | | | [c] 1 C | | | | | | [d] 1 B*2C | | | | | [c] 2 D | | | | | [d] 1 E | | | | | [e] 1 D/2E | | | | [d] D/E 2 G | | | | [e] 1 [d]*2G| | | [d] D/E*G 2= [b]-1[4] | | [b] B*C-D/E*G 3↑ H | | [c] 1 [b]*1H| [b] (B*C-D/E*G)*H 2↓ [a]+[b] [a] A+(B*C-D/E*G)*H 3↑ Fin */ #define cO gOutOpStk[ix] /* Fore easyer writing / reading */ for (ix = 0; ix < gOutOpStkLn; ix++) if (!cO._prec) { /// Operand Eval_DebugUniPrint(cO._compU, uP); // Get unary Tors string realVal = Eval_EvalOperand(cO._compU, cO._value); // Result applying them to Rand /// Op unary Tors, Rand string, Initial value, value after unary Tors #ifdef DEVEL_PARENTHESIZED printf("%-7s" _Cy("%-30s")" ($%04X -> $%04X)\n" , uP // Unary Tors string , cO._txt._opTorT // Rand string , cO._value // Inital value , realVal); // Final value #endif r = asprintf(&strP, "%s", cO._txt._opTorT); if (r < 0) Eval_ExitErr(kErr_MissMem); Eval_PushExp(strP, realVal, 1); // 1 -> Operand } else { Eval_DebugUniPrint(cO._compU, uP); // Prepare eventuel unary operators exp2 = Eval_PopExp(); // Get right term if (cO._prec < exp2->_prec // Put in between brasses f(precedence of Tor) && exp2->_prec > 1) { r = asprintf(&hStr, "(%s)", exp2->_string); if (r < 0) Eval_ExitErr(kErr_MissMem); free(exp2->_string); exp2->_string = hStr; // New bracketed expression } exp1 = Eval_PopExp(); // Get left term if (cO._prec < exp1->_prec // Put in between brasses if precedence of Tor && exp1->_prec > 1) { r = asprintf(&hStr, "(%s)", exp1->_string); if (r < 0) Eval_ExitErr(kErr_MissMem); free(exp1->_string); exp1->_string = hStr; // Done } // Evaluate whole expression tVal = Eval_EvalEpression(exp1->_value, cO._value, exp2->_value); realVal = Eval_EvalOperand(cO._compU, tVal); // Apply unary Tors r = asprintf(&strP, "%s%s%s" , exp1->_string // Left expression string , cO._txt._opTorT // Binaty Tor , exp2->_string); // Right expression string if (r < 0) Eval_ExitErr(kErr_MissMem); /// Op unary Tors, Rand or expr. string, left op. val, right op. val, after op, after una #ifdef DEVEL_PARENTHESIZED printf("%-7s"_Ja("%-30s")" %x " _Ro("%x")" %x ($%04X $%04X -> $%04X -> $%04X)\n" , uP // Unary Tors string , strP // Rand or expression string , exp1->_prec // Left expression precedence , cO._prec // Binary Tor precedence , exp2->_prec // Right expression precedence , exp1->_value // Left expression value , exp2->_value // Right xpression value , tVal // Initial result applying binary Tor , realVal); // Final result applying unary Tor to whole expres. #endif free(strP); r = asprintf(&strP, "%s%s%s" // Resulting expression's string , exp1->_string , cO._txt._opTorT , exp2->_string); if (r < 0) Eval_ExitErr(kErr_MissMem); free(exp1->_string); free(exp2->_string); Eval_PushExp(strP, realVal, cO._prec); // Push (back) expression } exp2 = Eval_PopExp(); // Get result printf("\n" _Ja("%s")" -> $" _Ro("%04X")"\n", exp2->_string, exp2->_value); free(exp2->_string); // Not necessary : just for valgrind ! #undef cO } int Main (int argc, char *argv[]) { /// ************************************************************************** char *strP; // NOTE usefull only if DEVEL_PARENTHESIZED is defined if (argc <= 1) { printf("No parameter in command line : add an Infix expression as first parameter.\n"); exit(EXIT_FAILURE); } if (asprintf(&strP, "0+(%s)", argv[1]) < 0) // if (asprintf(&strP, "%s", argv[1]) < 0) Eval_ExitErr(kErr_MissMem); printf("Infix expression : \"%s\"\n", strP); Eval_Infix2Postfix(strP); // To be converted printf("\nPostfix Expression: "); Eval_DebugPostPrint(0); free(strP); printf("\nBack to parenthesized expression:\n"); Eval_Postfix2Parent(); return 0; }