Cod sursa(job #2734511)

Utilizator Arteni_CristiArteni Cristi Arteni_Cristi Data 31 martie 2021 23:26:36
Problema Evaluarea unei expresii Scor 80
Compilator c-64 Status done
Runda Arhiva educationala Marime 4.16 kb
//120+(73-1+8)*(23-9)+10
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
 
#define MAX 100005
 
typedef struct stack{
    int data;
    struct stack *pred;
}stack;
 
int isEmpty(stack *);
int top(stack *);
void push(stack **, int);
int pop(stack **);
 
int isDigit(char);
int priority(char);
 
void infixToPostfix(char[], char[][50], int *);
 
void strrrev(char a[])
{
    int i = 0, j = strlen(a) - 1;

    while(i < j)
    {
        char aux = a[i];
        a[i] = a[j];
        a[j] = aux;
        i++;
        j--;
    }
}
 
int main()
{
    FILE *fin = fopen("evaluare.in", "r");
    FILE *fout = fopen("evaluare.out", "w");
 
    stack *final = NULL;
 
    char str[MAX];
    char newStr[MAX][50];
    int newSize = 0;
 
    fscanf(fin, "%[^\n]", str);

    //
    strrrev(str);
    for (int i =0 ; str[i]; i ++)
        if (str[i] == ')')
            str[i] = '(';
        else if (str[i] == '(')
            str[i] = ')';
    
    // fprintf(fout, "INVERS : %s\n", str);
    //
    infixToPostfix(str, newStr, &newSize);

    // fprintf(fout, "POSTFIX : ");
    // for (int i = 0; i < newSize; i ++)
    //     fprintf(fout, "%s ", newStr[i]);

    // fprintf(fout, "\nPREFIX : ");
    // for (int i = newSize - 1; i >= 0; i --)
    //     fprintf(fout, "%s ", newStr[i]);
 
    for (int i = 0; i < newSize; i ++)
    // for (int i = newSize - 1; i >= 0; i --)
        if (strlen(newStr[i]) == 1 && (newStr[i][0] < '0' || newStr[i][0] > '9'))
        {
            int b = pop(&final);
            int a = pop(&final);
            int c;
 
            switch(newStr[i][0])
            {
                case '+':
                    c = b + a;
                    break;
                case '-':
                    c = b - a;
                    break;
                case '/':
                    c = b / a;
                    break;
                default:
                    c = b * a;
            };
 
            push(&final, c);
        }
        else push(&final, atoi(newStr[i]));
 
 
    fprintf(fout, "%d\n", pop(&final));
    return 0;
}
 
void push(stack **root, int data)
{
    stack *temp = NULL;
    temp = (stack *)malloc(sizeof(stack));
 
    temp->data = data;
    temp->pred = NULL;
 
    if (*root == NULL)   
        *root = temp;
    else
    {
        temp->pred = *root;
        *root = temp;
    }
}
 
int top(stack *root)
{
    return root->data;
}
 
int isEmpty(stack *root)
{
    return !root;
}
 
int pop(stack **root)   
{
    int x = (*root)->data;
    *root = (*root)->pred;
 
    return x;
}
 
int isDigit(char x)
{
    return x >= '0' && x <= '9';
}
 
int priority(char x)
{
    switch (x)
    {
    case '-' :
    case '+' :
        return 1;
            
    case '/' :
    case '*' :
        return 2;
    }
 
    return -1;
}
 
void infixToPostfix(char str[], char newStr[][50], int *newSize)
{
    stack *operators = NULL;
 
    char number[15] = {0};
 
    for (int i = 0; str[i]; i ++)
    // for (int i = strlen(str) - 1; i >= 0; i --)
    {
        if (isDigit(str[i]))
        {
            number[strlen(number) + 1] = '\0';
            number[strlen(number)] = str[i];
 
            // if (i == 1 || !isDigit(str[i - 1]))
            if (i == strlen(str) - 1 || !isDigit(str[i + 1]))
            {
                //
                strrrev(number);
                //
                strcpy(newStr[*newSize], number);
                (*newSize) ++;
                number[0] = '\0';
            }
        } 
        else if (str[i] == '(')
            push(&operators, str[i]);
        else if (str[i] == ')')
        {
            while(!isEmpty(operators) && top(operators) != '(')
                newStr[(*newSize)++][0] = pop(&operators);
            pop(&operators);
        }
        else
        {
            while(!isEmpty(operators) && priority(str[i]) < priority(top(operators)))
                newStr[(*newSize)++][0] = pop(&operators);
            push(&operators, str[i]);
        }
    }
 
    while(!isEmpty(operators))
        newStr[(*newSize)++][0] = pop(&operators);
}