Организовать вычисление выражения, используя алгоритм польской записи

@john_jerome · Регистрация: 27.11.2010

Author24 — интернет-сервис помощи студентам

Дано выражение a*b+c*d.Организовать вычисление этого выражения, используя алгоритм польской записи. Применить программный стек.
нужно на С

silent_1991 · 18.03.2011, 19:09

Вики рулит

@john_jerome · 18.03.2011, 19:13 **[ТС]**

Я читал, но нифига не могу поянть
задачу нужно срочно сдать, поэтому и обращаюсь за помощью
если б было время - разобрался бы

silent_1991 · 18.03.2011, 21:08

Ага, сегодня задали... А сегодня в полночь - сдавать, иначе расстреляют.

Добавлено через 1 час 50 минут
Ладно, вот, когда-то страшно набыдлокодил, но изменять, естественно, ничего не собираюсь.

C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <math.h>
 
int syntax(char *exp, char *err, int *errpos);
int constParser(char *instr, char *outstr, int start, int end);
void unaryParser(char *);
int isOper(char);
int isOBkt(char);
int isCBkt(char);
int brackets(char *);
int priority(char);
void delSpaces(char *);
void simplification(char *);
void toRPN(char *exp, char *rpn);
double calculate(char *rpn, int *dbz);
 
//------------------------------------------------------------------------------
 
#define MAX_BUF 1024
 
int syntax(char *exp, char *err, int *errpos)
{
    int key;
    int i, j;
 
    for (i = 0, j = 0, key = 0; i < strlen(exp) - 1; i++)
        if (exp[i] != ' ' && exp[i] != '.' &&
            isOper(exp[i]) == 0 && isOBkt(exp[i]) == 0 &&
            isCBkt(exp[i]) == 0 && isdigit(exp[i]) == 0)
        {
            err[j] = exp[i];
            errpos[j++] = i;
            key = 1;
        }
 
    err[++j] = '\0';
 
    return key;
}
 
int constParser(char *instr, char *outstr, int start, int end)
{
    int ret;
    int i, j, k;
 
    k = 0;
    ret = 0;
 
    if (instr[start] == '_')
    {
        outstr[k++] = '-';
    }
    else
    {
        if (instr[start] == '=')
        {
            start++;
            ret = 1;
        }
    }
 
    for (i = k, j = k; i < end - start + 1; i++)
        outstr[j++] = instr[i + start];
 
    return ret;
}
 
void unaryParser(char *exp)
{
    int k;
 
    if (exp[0] == '-')
    {
        exp[0] = '_';
    }
    else
    {
        if (exp[0] == '+')
            exp[0] = '=';
    }
 
    for (k = 0; k < strlen(exp) - 1; k++)
    {
        if (exp[k] == '(')
        {
            k++;
 
            while (exp[k] == '(')
                k++;
 
            if (exp[k] == '-')
            {
                exp[k] = '_';
            }
            else
            {
                if (exp[k] == '+')
                    exp[k] = '=';
            }
        }
    }
}
 
//------------------------------------------------------------------------------
 
int isOper(char ch)
{
    if (ch == '+' ||
        ch == '-' ||
        ch == '*' ||
        ch == '/' ||
        ch == '^')
        return 1;
 
    return 0;
}
 
int isOBkt(char ch)
{
    if (ch == '(')
        return 1;
 
    return 0;
}
 
int isCBkt(char ch)
{
    if (ch == ')')
        return 1;
 
    return 0;
}
 
//------------------------------------------------------------------------------
 
int priority(char ch)
{
    if (ch == '^')
    {
        return 4;
    }
    else
    {
        if (ch == '*' || ch == '/')
        {
            return 3;
        }
        else
        {
            if (ch == '+' || ch == '-')
            {
                return 2;
            }
            else
            {
                if (ch == '(')
                    return 1;
            }
        }
    }
 
    return 0;
}
 
//------------------------------------------------------------------------------
 
int brackets(char *exp)
{
    int bkt;
    int i;
 
    for (i = 0, bkt = 0; i < strlen(exp) - 1; i++)
    {
        if (exp[i] == '(')
        {
            bkt++;
        }
        else
        {
            if (exp[i] == ')')
                bkt--;
        }
    }
 
    return bkt;
}
 
void delSpaces(char *exp)
{
    char buffer[MAX_BUF];
    int i, j;
 
    for (i = 0, j = 0; i < strlen(exp) - 1; i++)
        if (exp[i] != ' ')
            buffer[j++] = exp[i];
 
    buffer[j] = '\0';
 
    for (i = 0; i < strlen(buffer); i++)
        exp[i] = buffer[i];
 
    exp[i++] = '\0';
}
 
void simplification(char *exp)
{
    char buffer[MAX_BUF];
    int i, j;
 
    for (i = 0, j = 0; i < strlen(exp); i++)
    {
        while (exp[i] != '_' && exp[i] != '\0')
            buffer[j++] = exp[i++];
 
        if (exp[i + 1] == '(')
        {
            buffer[j++] = '_';
            buffer[j++] = '1';
            buffer[j++] = '*';
        }
        else
            buffer[j++] = exp[i];
    }
 
    buffer[j] = '\0';
 
    for (i = 0; i < strlen(buffer); i++)
        exp[i] = buffer[i];
 
    exp[i++] = '\0';
}
 
//------------------------------------------------------------------------------
 
void toRPN(char *exp, char *rpn)
{
    int p;
    int k, l;
    int i;
 
    char stack[MAX_BUF];
    int top;
 
    char temp[32];
 
    for (k = 0, p = 0, top = -1; k < strlen(exp); k++)
    {
        if (isdigit(exp[k]) != 0 || exp[k] == '_' || exp[k] == '=')
        {
            l = k;
 
            while (isdigit(exp[l + 1]) != 0 || exp[l + 1] == '.')
                l++;
 
            if (constParser(exp, temp, k, l) == 1)
                k++;
 
            for (i = 0; i < l - k + 1; i++)
                rpn[p++] = temp[i];
 
            rpn[p++] = ' ';
 
            k = l;
        }
        else
        {
            if (isOper(exp[k]) != 0)
            {
                if (exp[k] == '^')
                {
                    if (top == -1 || priority(stack[top]) <= priority(exp[k]))
                    {
                        stack[++top] = exp[k];
                    }
                    else
                    {
                        while (priority(stack[top]) > priority(exp[k]) && top != -1)
                        {
                            rpn[p++] = stack[top--];
                            rpn[p++] = ' ';
                        }
 
                        stack[++top] = exp[k];
                    }
                }
                else
                {
                    if (top == -1 || priority(stack[top]) < priority(exp[k]))
                    {
                        stack[++top] = exp[k];
                    }
                    else
                    {
                        while (priority(stack[top]) >= priority(exp[k]) && top != -1)
                        {
                            rpn[p++] = stack[top--];
                            rpn[p++] = ' ';
                        }
 
                        stack[++top] = exp[k];
                    }
                }
            }
            else
            {
                if (isOBkt(exp[k]) != 0)
                {
                    stack[++top] = exp[k];
                }
                else
                {
                    if (isCBkt(exp[k]) != 0)
                    {
                        while (priority(stack[top]) != 1)
                        {
                            rpn[p++] = stack[top--];
                            rpn[p++] = ' ';
                        }
 
                        top--;
                    }
                }
            }
        }
    }
 
    while (top != -1)
    {
        rpn[p++] = stack[top--];
        rpn[p++] = ' ';
    }
 
    rpn[--p] = '\0';
}
 
//------------------------------------------------------------------------------
 
double calculate(char *rpn, int *dbz)
{
    double stack[MAX_BUF];
    int top = -1;
 
    char temp[32];
 
    int k, l;
    int i;
 
    for (k = 0, top = -1; k < strlen(rpn); k++)
    {
        if (((isdigit(rpn[k]) != 0) || (rpn[k] == '-' && isdigit(rpn[k + 1]) != 0)))
        {
            l = k;
 
            while (isdigit(rpn[l + 1]) != 0 || rpn[l + 1] == '.')
                l++;
 
            for (i = 0; i < l - k + 1; i++)
                temp[i] = rpn[k + i];
 
            temp[i] = '\0';
            stack[++top] = atof(temp);
            k = l;
        }
        else
        {
            if (isOper(rpn[k]) != 0)
            {
                switch (rpn[k])
                {
                    case '+':
                    {
                        stack[top - 1] += stack[top];
                        top--;
                        break;
                    }
                    case '-':
                    {
                        stack[top - 1] -= stack[top];
                        top--;
                        break;
                    }
                    case '*':
                    {
                        stack[top - 1] *= stack[top];
                        top--;
                        break;
                    }
                    case '/':
                    {
                        if (stack[top] == 0.0)
                            *dbz = 1;
                        else
                        {
                            stack[top - 1] /= stack[top];
                            top--;
                            break;
                        }
                    }
                    case '^':
                    {
                        stack[top - 1] = pow(stack[top - 1], stack[top]);
                        top--;
                        break;
                    }
                }
            }
        }
    }
 
    return stack[0];
}
 
//------------------------------------------------------------------------------
 
int main(int argc, char **argv)
{
    char exp[MAX_BUF];
    char rpn[MAX_BUF];
    char err[MAX_BUF];
    int errpos[MAX_BUF];
 
    double result;
    int dbz = 0;
 
    int i;
 
    while (1)
    {
        printf("Enter arithmetic expression: ");
        fgets(exp, MAX_BUF, stdin);
 
        if (exp[0] == '\n')
            break;
 
        if (syntax(exp, err, errpos) != 0)
            for (i = 0; i < strlen(err); i++)
                printf("Invalid character \"%c\" at position %d\n", err[i], errpos[i]);
        else
        {
            if (brackets(exp) != 0)
                printf("Invalid placement of the brackets!");
            else
            {
                delSpaces(exp);
 
                if (exp[0] == '\0')
                {
                    printf("Empty expression!\n");
                    continue;
                }
 
                unaryParser(exp);
                simplification(exp);
                toRPN(exp, rpn);
                result = calculate(rpn, &dbz);
 
                if (dbz == 1)
                {
                    printf("Division by zero!\n");
                    continue;
                }
                else
                {
                    printf("Simplified expression: %s", exp);
                    printf("\nTransformed expression: %s", rpn);
                    printf("\nResult: %lf", result);
                }
            }
        }
 
        printf("\n");
    }
 
    return 0;
}

@john_jerome 47 / 47 / 1 Регистрация: 27.11.2010 Сообщений: 95
		1
	Организовать вычисление выражения, используя алгоритм польской записи 18.03.2011, 19:02. Показов 3383. Ответов 3 Метки нет (Все метки) Дано выражение ab+cd.Организовать вычисление этого выражения, используя алгоритм польской записи. Применить программный стек. нужно на С 0

silent_1991 5055 / 3115 / 271 Регистрация: 11.11.2009 Сообщений: 7,044
	18.03.2011, 19:09	2
	Вики рулит 0

@john_jerome 47 / 47 / 1 Регистрация: 27.11.2010 Сообщений: 95
	18.03.2011, 19:13 [ТС]	3
	Я читал, но нифига не могу поянть задачу нужно срочно сдать, поэтому и обращаюсь за помощью если б было время - разобрался бы 0

	18.03.2011, 21:08

Опции темы