Пример стека: преобразование формулы из инфиксной в постфиксную запись - EcsFlash/DataTypes GitHub Wiki

Исходный код - тут

Инфиксная запись: это стандартный формат записи математических выражений, где оператор находится между двумя операндами. Пример: a + b

Постфиксная запись: Это формат записи, в котором оператор следует после своих операндов. Пример: a b +

Алгоритм:

Обрабатываем каждый символ в инфиксной записи. Если символ - операнд, добавляем его в выходную строку. Если символ - оператор, помещаем его в стек, но перед этим выталкиваем из стека все операторы с большим или равным приоритетом. Если символ - открывающая скобка, помещаем ее в стек. Если символ - закрывающая скобка, выталкиваем из стека все операторы до открывающей скобки.

Функция проверки приоритета(если возвращается true, то будем вынимать операторы)

bool preor(char s,StackList<char>& stack)
{
	if (stack.isEmpty())
		return false;
	else if (s == '*' || s == '/')
	{
		if (stack.peek() == '*' || stack.peek() == '/')
			return true;
		else return false;
	}
	else if (s == '+' || s == '-')
	{
		if (stack.peek() == '(')
			return false;
		else return true;
	}
	return false;
}

В этом цикле написан алгоритм

for (int i = 0;i < (int)str.length();i++ )
	{
		if (str[i] != '+' && str[i] != '-' && str[i] != '/' && str[i] != '*' && str[i] != ')' && str[i] != '(') //only chars for ex.: a, b, etc
			newStr += str[i];
		else
		{
			if (str[i] == '(') {
				stack.addElem(str[i]);
			}
			else if (str[i] == ')')
			{
				while (!stack.isEmpty() && stack.peek() != '(')
				{
					newStr += stack.peek();
					stack.removeElem();
				}
				stack.removeElem();
			}
			else //only arifmetic operators
			{
				while (!stack.isEmpty() && preor(str[i],stack))
				{
					newStr += stack.peek();
					stack.removeElem();
				}
				stack.addElem(str[i]);
			}
		}

В конце вынимаем все операторы из стека

while (!stack.isEmpty())
	{
		newStr += stack.peek();
		stack.removeElem();
	}

обля

⚠️ **GitHub.com Fallback** ⚠️