Advertisement
STANAANDREY

expr eval using postfix/rev polish

Mar 7th, 2023 (edited)
1,081
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 2.19 KB | Science | 0 0
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <ctype.h>
  4. #include <string.h>
  5. #include <stdbool.h>
  6. #define NMAX 101
  7. #define SIGMA ('z' - 'a' + 1)
  8.  
  9. int opPrec(char op) {
  10.   if (strchr("+-", op)) {
  11.     return 1;
  12.   }
  13.   if (strchr("*/", op)) {
  14.     return 2;
  15.   }
  16.   return 0;//not op
  17. }
  18.  
  19. char *toPostfix(const char infix[]) {
  20.   const int n = strlen(infix);
  21.   int top = -1;
  22.   static char res[NMAX], st[NMAX];
  23.   for (int i = 0; i < n; i++) {
  24.     if (infix[i] == '(') {
  25.       st[++top] = infix[i];
  26.     } else if (infix[i] == ')') {
  27.       while (top >= 0 && st[top] != '(') {
  28.         strncat(res, &st[top--], 1);
  29.       }
  30.       top--;
  31.     } else if (opPrec(infix[i])) {
  32.       while (top >= 0 && opPrec(infix[i]) <= opPrec(st[top])) {
  33.         strncat(res, &st[top--], 1);
  34.       }
  35.       st[++top] = infix[i];
  36.     } else if (isalpha(infix[i])) {
  37.       strncat(res, &infix[i], 1);
  38.     }
  39.   }
  40.  
  41.   while (top >= 0) {
  42.     strncat(res, &st[top--], 1);
  43.   }
  44.   return res;
  45. }
  46.  
  47. int computeOp(int a, int b, char op) {
  48.   switch(op) {
  49.   case '+':
  50.     return a + b;
  51.   case '-':
  52.     return a - b;
  53.   case '*':
  54.     return a * b;
  55.   case '/':
  56.     return a / b;
  57.   }
  58.   return 0;//to supress warning
  59. }
  60.  
  61. int evalPostfixEx(const char postfix[], const int valOf[SIGMA]) {
  62.   static int st[NMAX];
  63.   int top = -1;
  64.   for (int i = 0; postfix[i]; i++) {
  65.     if (isalpha(postfix[i])) {
  66.       st[++top] = valOf[postfix[i] - 'a'];
  67.     } else {
  68.       int op2 = st[top--];
  69.       int op1 = st[top--];
  70.       int res = computeOp(op1, op2, postfix[i]);
  71.       st[++top] = res;
  72.     }
  73.   }
  74.   return st[top];
  75. }
  76.  
  77. int cntLetters(const char s[]) {
  78.   static bool used[SIGMA];
  79.   for (int i = 0; s[i]; i++) {
  80.     used[s[i] - 'a'] = true;
  81.   }
  82.   int cnt = 0;
  83.   for (int let = 0; let < SIGMA; let++) {
  84.     cnt += used[let];
  85.   }
  86.   return cnt;
  87. }
  88.  
  89. int main(void) {
  90.   static char infix[NMAX];
  91.   static int valOf[SIGMA];
  92.   if (!fgets(infix, NMAX, stdin)) {
  93.     perror("");
  94.     exit(-1);
  95.   }
  96.  
  97.   int nrLetters = cntLetters(infix);
  98.   for (int i = 0; i < nrLetters; i++) {
  99.     scanf("%d", &valOf[i]);
  100.   }
  101.  
  102.  
  103.   char *postfix = toPostfix(infix);
  104.   puts(postfix);
  105.   printf("%d\n", evalPostfixEx(postfix, valOf));//*/
  106.   return 0;
  107. }
  108.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement