Introduction to Programming (I)

Lab 12-2: Infix 整數指令列四則計算機 (40%)

• 輸入：包含整數 (符合 long 型態) 的四則計算運算式
  • 用空白字元分開整數數字及運算子，如：-1 + -2 * -3、1 * 2 + 3 - 4。
• 輸出：顯示使用者輸入的整數數字及運算子、以及運算結果。
  • 數字：-1 -2 -3、1 2 3 4。
  • 運算子：+ *、* + -。
  • 計算結果：-3 9、2 5 1。
• 檔名：lab12_2_<學號>.cpp (e.g. lab12_2_106062802.cpp)

Notice：

• 程式需提示使用者輸入運算式，程式需分析後顯示使用者輸入的整數數字及運算子。
• 程式需檢查數字跟運算子的數量是否相符，若不相符則顯示錯誤訊息 Invalid expression. 並結束程式。
  • Example：使用者輸入 4 個數字，但運算子只有 2 個，並非 3 個，則顯示錯誤訊息 Invalid expression. 並結束程式。
• 程式需檢查運算子是否為 '+'、'-'、'*'、'/'，若不相符則顯示錯誤訊息 Invalid expression. 並結束程式。
• 程式需檢查運算式是否為 Infix notation，若不相符則顯示錯誤訊息 Invalid expression. 並結束程式。
• 程式需依據 infix 的規則計算運算式，不考慮先乘除後加減，並將每步運算子的計算中間結果輸出。
  • Example：使用者輸入 -1 + -2 * -3，程式將計算結果為 -3 9。
• 程式需使用 function 來處理整數指令列四則計算機的輸入、計算與輸出。
• 程式需在 30 秒之內執行完畢，所有測資皆不會超過 30 秒的執行時間。

Format

Please input the expression: <expression, space seprated>⏎
Operands: <numbers, space seprated>
Operators: <operators, space seprated>
Result: <result>

Example

$ ./a.out⏎
Please input the expression: 1 * 2 + 3 - 4⏎
Operands: 1 2 3 4
Operators: * + -
Result: 2 5 1
$ ./a.out⏎
Please input the expression: -1 * -2 + -3 - -4⏎
Operands: -1 -2 -3 -4
Operators: * + -
Result: 2 -1 3
$ ./a.out⏎
Please input the expression: -1 + -2 * -3 - -4⏎
Operands: -1 -2 -3 -4
Operators: + * -
Result: -3 9 13
$ ./a.out⏎
Please input the expression: -1 * -2 + -3 -4⏎
Invalid expression.
$ ./a.out⏎
Please input the expression: -1 * -2 + -3 -⏎
Invalid expression.
$ ./a.out⏎
Please input the expression: -1 * -2 + -3 % -4⏎
Invalid expression.
$ ./a.out⏎
Please input the expression: 1 2 3 4 * + -⏎
Invalid expression.

Pseudo Code

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

using namespace std;

void parse_expression(const string &expression, vector<string> &tokens);
bool check_expression(const vector<string> &tokens);
string calculate_infix_expression(const vector<string> &tokens);
// hint: use std::to_string(long) to convert long to string
// see https://en.cppreference.com/w/cpp/string/basic_string/to_string
void print_ops(const vector<string> &tokens);
void print_nums(const vector<string> &tokens);

int main(int argc, char *argv[])
{
    string input_buffer;
    vector<string> tokens;

    cout << "Please input the expression: ";
    std::getline(cin, input_buffer);

    parse_expression(input_buffer, tokens);

    if (!check_expression(tokens))
    {
        cout << "Invalid expression." << endl;
        return EXIT_FAILURE;
    }

    print_ops(tokens);

    print_nums(tokens);

    cout << "Result: ";
    calculate_infix_expression(tokens);
    cout << endl;

    return EXIT_SUCCESS;
}

Reference:

• Lecture 8: Array & String (3) - example: a simple command line integer calculator

Reference Code:

Iterative:

Credit: 陳柏志 (107021128)

#include <cstdlib>
#include <iostream>
#include <string>
#include <vector>
#include <sstream>

using namespace std;

void parse_expression(const string &expression, vector<string> &tokens);
bool check_expression(const vector<string> &tokens);
string calculate_infix_expression(const vector<string> &tokens);
// hint: use std::to_string(long) to convert long to string
// see https://en.cppreference.com/w/cpp/string/basic_string/to_string
void print_ops(const vector<string> &tokens);
void print_nums(const vector<string> &tokens);

int main(int argc, char *argv[])
{
	string input_buffer;
	vector<string> tokens;

	cout << "Please input the expression: ";
	std::getline(cin, input_buffer);

	parse_expression(input_buffer, tokens);

	if (!check_expression(tokens))
	{
		cout << "Invalid expression." << endl;
		return EXIT_FAILURE;
	}

	print_nums(tokens);

	print_ops(tokens);

	cout << "Result:";
	calculate_infix_expression(tokens);
	cout << endl;

	return EXIT_SUCCESS;
}

void parse_expression(string const &expression, vector<string> &tokens)
{
	stringstream tokens_extractor(expression);

	for (string new_token; (tokens_extractor >> new_token);)
	{
		tokens.push_back(new_token);
	}
}

bool check_expression(const vector<string> &tokens)
{
	int op_cnt = 0, num_cnt = 0;

	for (int i = 0; i < tokens.size(); ++i)
	{
		if (i % 2 == 1)
		{
			if (tokens[i] == "+" 
				|| tokens[i] == "-" 
				|| tokens[i] == "*" 
				|| tokens[i] == "/")
				++op_cnt;
			else
				return false;
		}
		else
		{
			try
			{
				stol(tokens[i]);
				++num_cnt;
			}
			catch (const std::exception &e)
			{
				return false;
			}
		}
	}

	return num_cnt == op_cnt + 1;
}

string calculate_infix_expression(const vector<string> &tokens)
{
	if (tokens.size() == 0)
		return "";
	if (tokens.size() == 1)
	{
		cout << " " << tokens[0];
		return tokens[0];
	}

	long ans = stol(tokens[0]);
	for (int i = 1; i + 1 < tokens.size(); i += 2)
	{
		if (tokens[i] == "+")
			ans += stol(tokens[i + 1]);
		else if (tokens[i] == "-")
			ans -= stol(tokens[i + 1]);
		else if (tokens[i] == "*")
			ans *= stol(tokens[i + 1]);
		else if (tokens[i] == "/" && stol(tokens[i + 1]) != 0)
			ans /= stol(tokens[i + 1]);
		else
			cerr << endl
				 << "ERROR: divided by zero" << endl;
		cout << " " << ans;
	}

	return to_string(ans);
}

void print_ops(const vector<string> &tokens)
{
	cout << "Operators:";
	for (int i = 0; i < tokens.size(); ++i)
	{
		if (tokens[i] == "+" || tokens[i] == "-" 
			|| tokens[i] == "*" || tokens[i] == "/")
		{
			cout << " " << tokens[i];
		}
	}
	cout << endl;
}

void print_nums(const vector<string> &tokens)
{
	cout << "Operands:";
	for (int i = 0; i < tokens.size(); ++i)
	{
		try
		{
			long number = stol(tokens[i]);
			cout << " " << number;
		}
		catch (const std::exception &e)
		{
		}
	}
	cout << endl;
}

Recursive:

Credit: 陳光齊 (110021102)

#include <cstdlib>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <math.h>

using namespace std;

void parse_expression(const string &expression, vector<string> &tokens);
bool check_expression(const vector<string> &tokens);
void print_ops(const vector<string> &tokens);
void print_nums(const vector<string> &tokens);
bool string_isdigit(string s);
vector<string> calculate_infix_expression(vector<string> tokens);
void answer(const vector<string> &tokens);
long string_to_long(string s);

int main()
{
    string input_buffer;
    vector<string> tokens;

    cout << "Please input the expression: ";
    std::getline(cin, input_buffer);

    parse_expression(input_buffer, tokens);

    if (!check_expression(tokens))
    {
        cout << "Invalid expression." << endl;
        return 0;
    }
    print_nums(tokens);
    print_ops(tokens);

    cout << "Result:";
    if (tokens.size() == 1)
    {
        cout << " " << tokens[0];
    }
    else
    {
        tokens = calculate_infix_expression(tokens);
    }

    return 0;
}
void parse_expression(const string &expression, vector<string> &tokens)
{
    stringstream terms_extractor(expression);
    for (string term; (terms_extractor >> term);)
    {
        tokens.push_back(term);
    }
}
bool string_isdigit(string s)
{
    if (s[0] == '-')
    {
        if (s.size() == 1)
        {
            return false;
        }
        for (int i = 1; i < s.size(); i++)
        {
            if (!isdigit(s[i]))
            {
                return false;
            }
        }
        return true;
    }
    else
    {
        for (int i = 0; i < s.size(); i++)
        {
            if (!isdigit(s[i]))
            {
                return false;
            }
        }
        return true;
    }
}
bool check_expression(const vector<string> &tokens)
{
    int opcount = 0;
    int numcount = 0;
    for (int i = 0; i < tokens.size(); i++)
    {
        if (tokens[i] == "+" or tokens[i] == "-" 
            or tokens[i] == "*" or tokens[i] == "/")
        {
            opcount += 1;
        }
        else if (string_isdigit(tokens[i]))
        {
            numcount += 1;
        }
        else
        {
            return 0;
        }
    }
    if (numcount == opcount + 1)
    {
        for (int i = 1; i < tokens.size() - 1; i += 2)
        {
            if (!(tokens[i] == "+" or tokens[i] == "-" 
                or tokens[i] == "*" or tokens[i] == "/"))
            {
                return 0;
            }
        }
        return 1;
    }
    else
    {
        return 0;
    }
}
void print_ops(const vector<string> &tokens)
{
    cout << "Operators:";
    for (int i = 0; i < tokens.size(); i++)
    {
        if (tokens[i] == "+" or tokens[i] == "-" 
            or tokens[i] == "*" or tokens[i] == "/")
        {
            cout << " " << tokens[i];
        }
    }
    cout << endl;
}
void print_nums(const vector<string> &tokens)
{
    cout << "Operands:";
    for (int i = 0; i < tokens.size(); i++)
    {
        if (string_isdigit(tokens[i]))
        {
            cout << " " << tokens[i];
        }
    }
    cout << endl;
}
vector<string> calculate_infix_expression(vector<string> tokens)
{
    long a = 0;
    vector<string> vs;
    if (tokens.size() == 3)
    {

        if (tokens[1] == "+")
        {
            a = string_to_long(tokens[0]) + string_to_long(tokens[2]);
            cout << " " << a;
            string str = to_string(a);
            vs.push_back(str);
            return vs;
        }
        else if (tokens[1] == "-")
        {
            a = string_to_long(tokens[0]) - string_to_long(tokens[2]);
            cout << " " << a;
            string str = to_string(a);
            vs.push_back(str);
            return vs;
        }
        else if (tokens[1] == "*")
        {
            a = string_to_long(tokens[0]) * string_to_long(tokens[2]);
            cout << " " << a;
            string str = to_string(a);
            vs.push_back(str);
            return vs;
        }
        else if (tokens[1] == "/")
        {
            a = string_to_long(tokens[0]) / string_to_long(tokens[2]);
            cout << " " << a;
            string s = to_string(a);
            vs.push_back(s);
            return vs;
        }
    }
    else
    {
        if (tokens[tokens.size() - 2] == "+")
        {
            long temp = 0;
            temp = string_to_long(tokens[tokens.size() - 1]);
            tokens.pop_back();
            tokens.pop_back();
            a = string_to_long((calculate_infix_expression(tokens))[0]) + temp;
            cout << " " << a;
            string str = to_string(a);
            vs.push_back(str);
            return vs;
        }
        else if (tokens[tokens.size() - 2] == "-")
        {
            long temp = 0;
            temp = string_to_long(tokens[tokens.size() - 1]);
            tokens.pop_back();
            tokens.pop_back();
            a = string_to_long((calculate_infix_expression(tokens))[0]) - temp;
            cout << " " << a;
            string str = to_string(a);
            vs.push_back(str);
            return vs;
        }
        else if (tokens[tokens.size() - 2] == "*")
        {
            long temp = 0;
            temp = string_to_long(tokens[tokens.size() - 1]);
            tokens.pop_back();
            tokens.pop_back();
            a = string_to_long((calculate_infix_expression(tokens))[0]) * temp;
            cout << " " << a;
            string str = to_string(a);
            vs.push_back(str);
            return vs;
        }
        else if (tokens[tokens.size() - 2] == "/")
        {
            long temp = 0;
            temp = string_to_long(tokens[tokens.size() - 1]);
            tokens.pop_back();
            tokens.pop_back();
            a = string_to_long((calculate_infix_expression(tokens))[0]) / temp;
            cout << " " << a;
            string str = to_string(a);
            vs.push_back(str);
            return vs;
        }
    }
}
long string_to_long(string s)
{
    long a = 0;
    if (s[0] == '-')
    {
        for (int i = 1; i < s.size(); i++)
        {
            a *= 10;
            a += (s[i] - '0');
        }
        a *= -1;
        return a;
    }
    else
    {
        for (int i = s.size() - 1; i >= 0; i--)
        {
            a += (s[i] - '0') * pow(10, s.size() - 1 - i);
        }
        return a;
    }
}

Credit: 林暐晉 (110021134)

#include <cstdlib>
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <cctype>

using namespace std;

void parse_expression(const string &expression, vector<string> &tokens);
bool check_expression(const vector<string> &tokens);
string calculate_infix_expression(const vector<string> &tokens);
void print_ops(const vector<string> &tokens);
void print_nums(const vector<string> &tokens);

int main()
{
    string input_buffer;
    vector<string> tokens;

    cout << "Please input the expression: ";
    getline(cin, input_buffer);

    parse_expression(input_buffer, tokens);

    if (!check_expression(tokens))
    {
        cout << "Invalid expression." << endl;
        return EXIT_FAILURE;
    }

    print_nums(tokens);

    print_ops(tokens);

    cout << "Result:";
    if (tokens.size() == 1)
    {
        cout << tokens[0];
    }
    calculate_infix_expression(tokens);
    cout << endl;

    return EXIT_SUCCESS;
}

void parse_expression(const string &expression, vector<string> &tokens)
{
    stringstream stream_ex(expression);
    for (string s; stream_ex >> s;)
    {
        tokens.push_back(s);
    }
}

bool check_expression(const vector<string> &tokens)
{
    unsigned long long num = 0, op = 0;
    bool bool_before = 0, bool_after = 0;
    for (int i = 0; i < tokens.size(); i++)
    {
        bool n = 0;
        for (int j = 0; j < tokens[i].size(); j++)
        {
            if (tokens[i] == "+" || tokens[i] == "-" 
                || tokens[i] == "*" || tokens[i] == "/")
            {
                op += 1;
                bool_after = 0;
                break;
            }
            else if (tokens[i][j] == '-')
            {
                if (j != 0)
                {
                    return 0;
                }
            }
            else if (isdigit(tokens[i][j]))
            {
                n = 1;
            }
            else
            {
                return 0;
            }
        }
        if (n == 1)
        {
            num += 1;
            bool_after = 1;
        }
        if (bool_after == bool_before)
        {
            return 0;
        }
        bool_before = bool_after;
    }
    if (num - op != 1)
    {
        return 0;
    }
    return 1;
}

string calculate_infix_expression(const vector<string> &tokens)
{
    if (tokens.size() == 1)
    {
        return tokens[0];
    }
    vector<string> left(tokens.begin(), tokens.end() - 2),
        right(tokens.end() - 2, tokens.end());

    string ans;
    if (right[0] == "+")
    {
        ans = to_string(stol(calculate_infix_expression(left)) + stol(right[1]));
        cout << " " << ans;
        return ans;
    }
    else if (right[0] == "-")
    {
        ans = to_string(stol(calculate_infix_expression(left)) - stol(right[1]));
        cout << " " << ans;
        return ans;
    }
    else if (right[0] == "*")
    {
        ans = to_string(stol(calculate_infix_expression(left)) * stol(right[1]));
        cout << " " << ans;
        return ans;
    }
    else if (right[0] == "/")
    {
        ans = to_string(stol(calculate_infix_expression(left)) / stol(right[1]));
        cout << " " << ans;
        return ans;
    }
    else
    {
        return "qwertyuiop";
    }
}

void print_nums(const vector<string> &tokens)
{
    cout << "Operands:";
    for (int i = 0; i < tokens.size(); i++)
    {
        bool n = 0;
        if (tokens[i] == "+" || tokens[i] == "-" 
            || tokens[i] == "*" || tokens[i] == "/")
        {
            n = 1;
        }
        if (n == 0)
        {
            cout << " " << tokens[i];
        }
    }
    cout << endl;
}

void print_ops(const vector<string> &tokens)
{
    cout << "Operators:";
    for (int i = 0; i < tokens.size(); i++)
    {
        bool n = 0;
        if (tokens[i] == "+" || tokens[i] == "-" 
            || tokens[i] == "*" || tokens[i] == "/")
        {
            n = 1;
        }
        if (n == 1)
        {
            cout << " " << tokens[i];
        }
    }
    cout << endl;
}

TA version:

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

using namespace std;

void parse_expression(const string &expression, vector<string> &tokens);
bool check_expression(const vector<string> &tokens);
void calculate_infix_expression(const vector<string> &tokens);
// hint: use std::to_string(long) to convert long to string
// see https://en.cppreference.com/w/cpp/string/basic_string/to_string
void print_ops(const vector<string> &tokens);
void print_nums(const vector<string> &tokens);

int main(int argc, char *argv[])
{
    string input_buffer;
    vector<string> tokens;

    cout << "Please input the expression: ";
    std::getline(cin, input_buffer);

    parse_expression(input_buffer, tokens);

    if (!check_expression(tokens))
    {
        cout << "Invalid expression." << endl;
        return EXIT_FAILURE;
    }

    print_nums(tokens);

    print_ops(tokens);

    cout << "Result: ";
    calculate_infix_expression(tokens);
    cout << endl;

    return EXIT_SUCCESS;
}

bool is_number(string str)
{
    for (int i = 0; i < str.length(); i++)
    {
        if (i == 0 && str[i] == '-' && str.length() > 1)
            continue;
        if (!isdigit(str[i]))
            return false;
    }
    return true;
}

void parse_expression(const string &expression, vector<string> &tokens)
{
    string temp;
    for (int i = 0; i < expression.size(); i++)
    {
        if (expression[i] == ' ')
        {
            tokens.push_back(temp);
            temp.clear();
        }
        else if (i == expression.size() - 1) // End of Input_Buffer
        {
            temp += expression.substr(i, 1);
            tokens.push_back(temp);
        }
        else
            temp += expression.substr(i, 1);
    }
}

bool check_expression(const vector<string> &tokens)
{
    int oper_counts = 0, num_counts = 0;
    for (int i = 0; i < tokens.size(); i++)
    {
        if (tokens[i] == "+" || tokens[i] == "-" 
            || tokens[i] == "*" || tokens[i] == "/")
            oper_counts++;
        else if (is_number(tokens[i]))
            num_counts++;
        else
            return false;

        if (num_counts != oper_counts + (i + 1) % 2)
            return false;
    }
    if (!is_number(tokens[tokens.size() - 1]))
        return false;
    return true;
}

void print_nums(const vector<string> &tokens)
{
    cout << "Operands:";
    for (int i = 0; i < tokens.size(); i++)
    {
        if (tokens[i].length() != 1 || isdigit(tokens[i][0]))
            cout << ' ' << tokens[i];
    }
    cout << endl;
}

void print_ops(const vector<string> &tokens)
{
    cout << "Operators:";
    for (int i = 0; i < tokens.size(); i++)
    {
        if (tokens[i].length() == 1 && !isdigit(tokens[i][0]))
            cout << ' ' << tokens[i];
    }
    cout << endl;
}

void calculate_infix_expression(const vector<string> &tokens)
{
    if (tokens.size() == 1)
    {
        cout << tokens[0];
        return;
    }

    long a, b;

    for (int i = 0; i < tokens.size() - 2; i += 2)
    {
        if (i == 0)
            a = stol(tokens[i]);
        b = stol(tokens[i + 2]);

        if (tokens[i + 1] == "+")
            a += b;
        else if (tokens[i + 1] == "-")
            a -= b;
        else if (tokens[i + 1] == "*")
            a *= b;
        else if (tokens[i + 1] == "/")
            a /= b;

        cout << a << ' ';
    }
    return;
}