сложение и умножение строки в C ++

Question

Я делаю домашнее задание на C ++, но не могу понять алгоритм.

Мне нужно создать программу, которая работает со строками.

Строки и операторы (+ и *) должны быть дифференцированным по пробелу ('')

, и умножение выполняется первым, а не сложение

+) используйте atoi, чтобы изменить строку на целое

, например:

ВХОД: ab c + b * 4 + xy * 2 + z

ВЫХОД: abcbbbbxyxyz

до сих пор это то, что я сделал ↓

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include<sstream>
using namespace std;

enum classify {NUMBER, STRING, OPERATION, SPACE};

int char_type(string c)
{
        if (c >= "0" && c <= "9") return NUMBER;
        else if (c == "*" || c == "+") return OPERATION;
        else if (c == " ") return SPACE;
        else return STRING;
}

int main(void)
{
        string input;
        getline(cin, input);
        istringstream token(input);
        string buffer;

        while (getline(token, buffer, ' '))
                { after I classify them using enum, how can I
                  let the computer to know "multiplication first"? }
}

Answer 1

Я не могу понять алгоритм.

Один канонический способ - преобразовать ваше математическое выражение инфикса в нотацию Reverse Poli sh и затем оценить его. Подробнее см. https://en.wikipedia.org/wiki/Shunting-yard_algorithm.

Answer 2

Я на самом деле новичок в C ++, поэтому мне было трудно понять код Тогги Смита

Но я смог сделать его короче!

#include <iostream>
#include <string>
#include <vector>
#include<sstream>
using namespace std;

enum classify { NUMBER, STRING };
typedef vector<string> Tokens;

Tokens tokenize(string input, string token)
{
    istringstream list(input);
    Tokens v;
    while (getline(list, token, ' '))
        v.push_back(token);
    return v;
}

int char_type(string c)
{
    if (c >= "0" && c <= "9") return NUMBER;
    else return STRING;
}

Tokens remove_empty(Tokens tokens)
{
    Tokens newTokens;
    for (int i = 0; i < tokens.size(); i++)
    {
        if (tokens[i] != "")
        {
            newTokens.push_back(tokens[i]);
        }
    }
    return newTokens;
}

Tokens multiply(Tokens tokens)
{
    for (int i = 0; i < tokens.size(); i++)
    {
        if (tokens[i] == "*")
        {
            string* left = &tokens[i - 1];
            string* right = &tokens[i + 1];
            int left_type = char_type(*left);
            int right_type = char_type(*right);

            if (left_type == NUMBER)
            {
                int number = stoi(*left);
                string tempString;
                for (int j = 0; j < number; j++)
                    tempString += *right;
                *left = tempString;
                tokens[i] = "";
                *right = "";
            }
            else if (right_type == NUMBER)
            {
                int number = stoi(*right);
                string tempString;
                for (int j = 0; j < number; j++)
                    tempString += *left;
                *left = tempString;
                tokens[i] = "";
                *right = "";
            }
        }
    }
    tokens = remove_empty(tokens);
    return tokens;
}

Tokens add(Tokens tokens)
{
    for (int i = 0; i < tokens.size(); i++)
    {
        if (tokens[i] == "+")
        {
            string* left = &tokens[i - 1];
            string* right = &tokens[i + 1];
            *left += *right;
            tokens[i] = "";
            *right = "";
        }
    }
    tokens = remove_empty(tokens);
    return tokens;
}

string tok_to_str(Tokens tokens)
{
    string tempString;
    for (int i = 0; i < tokens.size(); i++)
        tempString += tokens[i];
    return tempString;
}

int main(void)
{
    string input;
    cout << "입력 >> ";
    getline(cin, input);

    istringstream list(input);
    string token;

    // Tokenize
    Tokens tokens = tokenize(input, token);

    // Multiplication
    tokens = multiply(tokens);

    // Addition
    tokens = add(tokens);

    // Tokens to Strings
    string output = tok_to_str(tokens);

    cout << output;
}

Answer 3

Алгоритм:

• Преобразование входной строки в токены. Жетоны разделены пробелами. Например, «ab c + b * 4 + xy * 2 + z» преобразуется в токены «ab c», «b», «», «4», «+», «xy». ",""," 2 "," + "и" z ".
• Выполнение операций умножения.
  • Go через токены один за другим.
  • Если токен является знаком умножения ("*"):
    • Определите, является ли токен до или после это число, которое является числом.
    • Если токен перед номером:
      • Создать временную строку, многократно добавлять токен после (букв) во временную строку для числа количество раз, указанное токеном до (число).
    • Если токен после является числом:
      • Создать временную строку, многократно добавлять токен до ( букв) во временную строку для числа раз, указанного токеном после (число).
    • Установите токен перед временной строкой.
    • Сделайте текущий токен (знак умножения) и следующий токен пустые токены.
  • Удаление пустых токенов.
• Выполните операции сложения.
  • Go по токенам один за другим.
  • Если токен является знаком добавления ("*"):
    • Конкатенация токена после конца токена до.
    • Сделать текущий токен (знак умножения) и следующий токен пустыми токенами.
  • Удалить пустые токены.
• Преобразование токенов обратно в строку.

Код:

#include <iostream>
#include <string>
#include <vector>

typedef std::string Token;
typedef std::vector<Token> Tokens;

Tokens tokenise(std::string str)
{
    Tokens tokens;

    int startOfToken = 0;

    // Move through until you find a space (" ") and then add the token (the start of the token is the previous space) and the end is the current space
    for (int i = 0; i < str.size(); i++)
    {
        if (str.substr(i, 1) == " ")
        {
            tokens.push_back(str.substr(startOfToken, i - startOfToken));

            startOfToken = i + 1;
        }
    }

    // Add last token (there is no space after it to mark it)
    tokens.push_back(str.substr(startOfToken));

    return tokens;
}

bool containsNumber(Token token)
{
    if (token.find("0") != std::string::npos)
    {
        return true;
    }
    else if (token.find("1") != std::string::npos)
    {
        return true;
    }
    else if (token.find("2") != std::string::npos)
    {
        return true;
    }
    else if (token.find("3") != std::string::npos)
    {
        return true;
    }
    else if (token.find("4") != std::string::npos)
    {
        return true;
    }
    else if (token.find("5") != std::string::npos)
    {
        return true;
    }
    else if (token.find("6") != std::string::npos)
    {
        return true;
    }
    else if (token.find("7") != std::string::npos)
    {
        return true;
    }
    else if (token.find("8") != std::string::npos)
    {
        return true;
    }
    else if (token.find("9") != std::string::npos)
    {
        return true;
    }

    return false;
}

Tokens removeEmptyTokens(Tokens tokens)
{
    Tokens newTokens;

    for (int i = 0; i < tokens.size(); i++)
    {
        // Only add token to new tokens if it isn't empty
        if (tokens[i] != "")
        {
            newTokens.push_back(tokens[i]);
        }
    }

    return newTokens;
}

Tokens performMultiplicationOperations(Tokens tokens)
{
    // Iterate through the tokens
    for (int i = 0; i < tokens.size(); i++)
    {
        // If a token is a multiplication sign ("*")
        if (tokens[i] == "*")
        {
            // Store token before sign and after sign
            std::string* previousToken = &tokens[i - 1];
            std::string* nextToken = &tokens[i + 1];

            // Find out whether the previous token or the next token is a number
            bool tokenThatIsNumber = containsNumber(*nextToken); // False if previous token is a number, true if next token is a number

            // If previous token is a number:
            if (tokenThatIsNumber == false)
            {
                // Convert previous token to a number
                int previousTokenAsInteger = std::stoi(*previousToken);

                // Temp variable to store final string
                std::string tempString;

                // Add next token to temp string as many times as previous token specifies
                for (int j = 0; j < previousTokenAsInteger; j++)
                {
                    tempString += *nextToken;
                }

                // Set previous token to temp string
                *previousToken = tempString;

                // Get rid of current token ("*") and next token
                tokens[i] = "";
                *nextToken = "";
            }
            // If next token is a number:
            else
            {
                // Convert next token to a number
                int nextTokenAsInteger = std::stoi(*nextToken);

                // Temp variable to store final string
                std::string tempString;

                // Add previous token to temp string as many times as next token specifies
                for (int j = 0; j < nextTokenAsInteger; j++)
                {
                    tempString += *previousToken;
                }

                // Set previous token to temp string
                *previousToken = tempString;

                // Make current token ("*") and next token empty
                tokens[i] = "";
                *nextToken = "";
            }
        }
    }

    // Remove empty tokens
    tokens = removeEmptyTokens(tokens);

    return tokens;
}

Tokens performAdditionOperations(Tokens tokens)
{
    // Iterate through the tokens
    for (int i = 0; i < tokens.size(); i++)
    {
        // If a token is an addition sign ("+")
        if (tokens[i] == "+")
        {
            // Store token before sign and after sign
            std::string* previousToken = &tokens[i - 1];
            std::string* nextToken = &tokens[i + 1];

            // Concatenate next token onto end of previous token
            *previousToken += *nextToken;

            // Make current token ("+") and next token empty
            tokens[i] = "";
            *nextToken = "";
        }
    }

    // Remove empty tokens
    tokens = removeEmptyTokens(tokens);

    return tokens;
}

std::string tokensToString(Tokens tokens)
{
    std::string tempString;

    for (int i = 0; i < tokens.size(); i++)
    {
        tempString += tokens[i];
    }

    return tempString;
}

int main()
{
    // Get user input
    std::string input = "";

    std::cout << "Please enter something: ";

    std::getline(std::cin, input);

    // Tokenise
    Tokens tokens = tokenise(input);

    // Perform multiplication operations
    tokens = performMultiplicationOperations(tokens);

    // Perform addition operations
    tokens = performAdditionOperations(tokens);

    // Convert tokens to strings
    std::string finalString = tokensToString(tokens);

    std::cout << finalString;
}