Преобразование строки с мат. выражение

[Sobakaa]

Дано - пользователь ввёл строку, например ((5+2)*2), необходимо вычислить её. Пятый час пробую подойти с разных сторон, но ничего не придумывается.
Можно вычислять сперва внутреннее выражение, дойдя до первой закрывающей скобки. Потом доходить до второй, возвращаться на два символа назад и выполнять операцию между уже вычисленным и текущим. Потом искать следующую закрывающую и так до полного счастья.
Но вот запрограммировать это руки не поднимаются. Подскажите, идея имеет потенциал? Или есть более изящное решение?

[_SG]

Обратная польская запись тебе поможет. И гугл)
Если честно, я очень давно писал компиляторы (ещё на студенческой скамье)
неплохая статья в википедии

[Newbie]

Напишу за небольшое вознаграждение.) ася 590445302

А вообще ты мыслишь в правильном направлении:
"Можно вычислять сперва внутреннее выражение, дойдя до первой закрывающей скобки"
но сначала надо искать последнюю раскрывающуюся.
Единственное, что остается это определить приоритет операций и вычислить.

[_SG]

Алгоритм Дейкстры (или как там его) для перевода в обратную польскую, а там уж и вычислить не сложно.

[Romeo]

В бытность мою студентом я написал полноценный анализотор и калькулятор математических выражений. Спешу поделиться идеями.

Введём некоторые определения.

Будем говорить, что некий символ S в исходной строке имет скобочную вложенность = N, если этот символ окружён N скобками.

( ... ( S ) ... )
\-----/ \-----/
N скобок N скобок

Все математические операции разобьём по трём приоритетам.
Операции 1-го приоритета: ^ (возведение в степень)
Операции 2-го приоритета: *, /
Операции 3-го приоритета: +, -

Наша задача реализовать функцию calc следующего вида.

Код: Выделить всё

float calc(char* str);

P.S. Почему входную строку не стоит делать const, станет видно позже.

Перед тем, как передать строку внутрь функции calc давайте проделаем некие действия, которые упростят нам жизнь в будущем.

- Удалим из строки все символы пробелов и знаки табуляции;
- Проведём предварительный анализ скобок. Здесь проще привести готовый кусок кода, так как описывать, что именно он делает будет дольше.

Код: Выделить всё

int nBr = 0; // текущая скобочная вложенность
for (const char* p = str; ++p; *p != '\0')
{
   if (*p == '(') ++bBr;
   else if (*p == '(') --bBr;
   
   if (nBr < 0) break;
}

if (nBr)
{
   std::cerr << "Error of bracket balance" << std::end;
   exit(1);
}

На этом этапе у нас получится забраковать следующие варианты:
(1
1+2)
)3(

Далее обработанная и предварительно проверенная строка должна быть передана в функцию calc. Рассмотрим, что должна делать эта функция.

0. Если строка str пустая (то есть её первый символ равен знаку окончания строки '\0'), то рапортуем об ошибке.

1. В самом начале функции должен стоять цикл удаления лишних скобок. Если самый первый и самый последний символ в строке это '(' и ')' и ни один символ в строке не имеет скобочную вложенность = 0, то мы можем смело удалить первый и последний символ.

Примеры:
((5)) -> 5
(2+3) -> 2+3.

Проверка на отсутствие символа со скобочной вложенностью равной 0, позволит не применить упрощение к следующему выражению: (2)+(3) -> 2)+(3, ведь стоящее в правой части - полный бред.

2. Следующий шаг - поиск знаков операций с нулевой скобочной вложенностью. Сначала ищится первый встречный знак 3-го приоритета. Если не найден, то делается ещё проход в поисках знака операции 2-го приоритета и только затем первого.

Примеры:
2+3, найден +
2*3, найден *
2*3+4, найден +, так как у него приоритет меньше, значит он будет искаться раньше *
2*(3+4), найден *, так как у + не нулевая скобочная вложенность.
4, не найдено ничего.
(5+6)(7), не найдено ничего

3. Если после трёх проходов не было обнаружено ни одного знака с нулевой скобочной вложенностью, то преверяем есть ли в выражении хоть ода скобка (не важно открывающаяся или закрывающаяся). Если есть, то выкидываем ошибку (в примере последняя строки являются ошибкой). Если скобок нет, то перегоняем строку в float и возвращаем её. Для этого этого можно воспользоваться либо функциями типа atof, либо STL.

4. Теперь самое интересное. Что же делать, если знак найден. Найденный знак операци мы запоминаем во временной переменной и на его место в строке вставляем знак конца строки - '\0'. Далее вызываем рекурсивно функцию calc для левой и правой части строки. Благодаря тому, что строку мы не сделали const, мы сможем работать в одном буфере и перевыделяя память на новые строки. К результатам двух рекурсивных вызовов функции calc следует применить математическую операцию взависимости от символа операции, который был сохранён во временную переменную. Вот набросок кода для этой части:

Код: Выделить всё

// предположим, что после трёх проходов поиска, в переменной pSign
// хранится адрес символа, в котором был найден требуемый знак.
const char nSign = *pSign; // сохраняем символ знака во временную переменную
*pSign = '\0'; // обрезали строку, теперь у нас две строки: одна слева от поставленного '\0', вторая справа.
switch (nSign)
{
   case '-': return calc(str) - calc(pSign+1);
   case '+': return calc(str) + calc(pSign+1);
   // и так далее для всех оставшихся операций
}

Вот и вся премудрость. Если что, спрашивай - помогу.

[Sobakaa]

Код: Выделить всё

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <ctype.h>
#include <assert.h>

int group; //temporary number for memorizing current calculation
double groupval; //calculated number

//the main function, checks EOF, ' ', floats and incorrect input. 
//Deals with +-*=()/ and manipulate other functions.
int next()
{
	while(1)
	{
        int c = getchar();
        if (c == EOF || strchr("+-*/^()\n", c) != NULL)
			return group = c;
        if (isspace(c)) 
			continue;
        if (isdigit(c) || c == '.')
		{
            ungetc(c, stdin);
            scanf(" %lf", &groupval);
            return group = 'n';
        }
        fprintf(stderr, "Bad character: %c\n", c);
    }
}
//skiping symbols like ( and ) after
void skip(int t)
{
	assert(group == t); 
	next(); 
}

double expr(void);
// Dealing with ( and ) and continuing to calculate
double numpar(void) 
{
    if (group == 'n') 
	{ 
		double x = groupval;
		skip('n'); return x; 
	}
    skip('('); 
	double x = expr(); 
	skip(')');
	return x;
}
// Dealing with pow.
double factor(void) 
{
    double x = numpar();
    if (group == '^') 
	{ 
		skip('^'); x = pow(x, factor()); 
	}
    return x;
}
// Dealing with * and /
double term(void) {
    double x = factor();
    while(1)
	{
        if (group == '*') 
		{ 
			skip('*'); x *= factor(); 
		}
        else if (group == '/') 
		{ 
			skip('/'); x /= factor(); 
		}
        else return x;
    }
}
//Dealing with + and -
double expr(void) {
    double x = term();
    while(1)
	{
        if (group == '+') 
		{ 
			skip('+'); 
			x += term(); 
		}
        else if (group == '-') 
		{ 
			skip('-'); 
			x -= term(); 
		}
        else return x;
    }
}
//the main function. calls next, checks for EOF to stop
int main() 
{
    next();
    while (group != EOF) 
	{
        if (group == '\n') 
		{ 
			skip('\n'); 
			continue;
		}
        printf("%.9g\n", expr());
    }
    return 0;
}

Нашёл в инете пример функции некст, скип и сложения. Остальное кое-как реализовал сам. Правда из-за того, что они рекурсивно вызывают по кругу самих себя, пришлось-таки ввести одно описание функции, отвечающей за сложение.
Этакий Хаффман на функциях получился. Правда благодаря потыренному нексту и скипу он и без скобок работает.
Слава кому-то.

[_SG]

(( Уровень математического образования программистов упал(( Зачем изобретать велосипед в ТАКОЙ области. Давно уже разработаны принципы построения компиляторов/интерпритаторов.