Introduction to Programming (I)

Lab 12-3: Postfix 整數指令列四則計算機 (20%)

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

Notice：

• 程式需提示使用者輸入運算式，程式需分析後顯示使用者輸入的整數數字及運算子。
• 程式需檢查數字跟運算子的數量是否相符，若不相符則顯示錯誤訊息 Invalid expression. 並結束程式。
  • Example：使用者輸入 4 個數字，但運算子只有 2 個，並非 3 個，則顯示錯誤訊息 Invalid expression. 並結束程式。
• 程式需檢查運算子是否為 '+'、'-'、'*'、'/'，若不相符則顯示錯誤訊息 Invalid expression. 並結束程式。
• 程式需檢查運算式是否為 Postfix notation，若不相符則顯示錯誤訊息 Invalid expression. 並結束程式。
• 程式需依據 postfix 的規則計算運算式，並將每步運算子的計算中間結果輸出。
  • Example：使用者輸入 1 2 3 4 * + -，程式將計算結果為 12 14 -13。
• 程式需使用 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: 12 14 -13
$ ./a.out⏎
Please input the expression: -1 -2 -3 -4 * + -⏎
Operands: -1 -2 -3 -4
Operators: * + -
Result: 12 10 -11
$ ./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 - 2 1 + /⏎
Operands: 1 2 2 1
Operators: - + /
Result: -1 3 0
$ ./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_postfix_expression(vector<string> &tokens, int &last_pos);
// hint: use std::to_string(long) to convert long to string
// see https://en.cppreference.com/w/cpp/string/basic_string/to_string
// hint: use recursion to find the subexpressions of two operands
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: ";
    int last_pos = tokens.size() - 1;
    calculate_postfix_expression(tokens, last_pos);
    cout << endl;

    return EXIT_SUCCESS;
}

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_postfix_expression(vector<string> &tokens, int &last_pos);
// hint: use std::to_string(long) to convert long to string
// see https://en.cppreference.com/w/cpp/string/basic_string/to_string
// hint: use recursion to find the subexpressions of two operands
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:";
	int last_pos = tokens.size() - 1;
	calculate_postfix_expression(tokens, last_pos);
	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;
	int number_in_stack_cnt = 0;

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

	return num_cnt == op_cnt + 1 && number_in_stack_cnt == 1;
}

string calculate_postfix_expression(vector<string> &tokens, int &last_pos)
{
	if (tokens.size() == 1)
	{
		cout << " " << tokens[0];
		return tokens[0];
	}
	vector<long> numbers;

	for (int i = 0; i < tokens.size(); ++i)
	{
		if (tokens[i] == "+" || tokens[i] == "-" 
			|| tokens[i] == "*" || tokens[i] == "/")
		{
			long b = numbers.back();
			numbers.pop_back();
			long a = numbers.back();
			numbers.pop_back();
			if (tokens[i] == "+")
				numbers.push_back(a + b);
			else if (tokens[i] == "-")
				numbers.push_back(a - b);
			else if (tokens[i] == "*")
				numbers.push_back(a * b);
			else if (b != 0)
				numbers.push_back(a / b);
			else
			{
				numbers.push_back(a);
				cerr << endl
					 << "ERROR: divided by zero" << endl;
			}
			cout << " " << numbers.back();
		}
		else
		{
			numbers.push_back(stol(tokens[i]));
		}
	}
	return to_string(numbers.back());
}

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: 林元鴻 (110021120)

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

void parse_expression(string &expression, vector<string> &tokens)
{
    stringstream str(expression);
    for (string term; (str >> term);)
    {
        tokens.push_back(term);
    }
}
bool check_expression(const vector<string> &tokens, int &n)
{
    int o = 0;

    for (int i = 0; i < tokens.size(); i++)
    {
        if (tokens[i] == "+" || tokens[i] == "-" 
            || tokens[i] == "*" || tokens[i] == "/")
        {
            n++;
        }
        else
        {
            for (int j = 0; j < tokens[i].size(); j++)
            {
                if (j == 0 && (!isdigit(tokens[i][j]) && tokens[i][j] != '-'))
                    return false;
                else if (!isdigit(tokens[i][j]) && j != 0)
                    return false;
            }
            o++;
        }
    }
    return (o == n + 1);
}
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++)
    {
        if (!(tokens[i] == "+" || tokens[i] == "-" 
            || tokens[i] == "*" || tokens[i] == "/"))
        {
            cout << stol(tokens[i]) << ' ';
        }
    }
    cout << endl;
}
string calculate_postfix_expression(
    vector<string> &tokens, 
    int &last_pos, 
    vector<string> &final_ans)
{
    if (tokens.size() == 1)
    {
        return tokens[0];
    }
    int n = last_pos, o = last_pos;
    long b, a;
    string ans, re;
    last_pos--;
    n = last_pos;
    if (last_pos < 0)
        return "error";
    if (tokens[last_pos] == "+" || tokens[last_pos] == "-" 
        || tokens[last_pos] == "*" || tokens[last_pos] == "/")
    {
        re = calculate_postfix_expression(tokens, last_pos, final_ans);
        if (re == "error")
            return "error";
        else
        {
            b = stol(re);
            final_ans[n] = re;
        }
    }
    else
        b = stol(tokens[last_pos]);
    last_pos--;
    n = last_pos;
    if (last_pos < 0)
        return "error";
    if (tokens[last_pos] == "+" || tokens[last_pos] == "-" 
        || tokens[last_pos] == "*" || tokens[last_pos] == "/")
    {
        re = calculate_postfix_expression(tokens, last_pos, final_ans);
        if (re == "error")
            return "error";
        else
        {
            a = stol(re);
            final_ans[n] = re;
        }
    }
    else
        a = stol(tokens[last_pos]);

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

    ans = to_string(a);
    return ans;
}
int main(int argc, char *argv[])
{
    string input_buffer, str;
    vector<string> tokens;

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

    parse_expression(input_buffer, tokens);
    int n = 0;
    if (!check_expression(tokens, n))
    {
        cout << "Invalid expression." << endl;
        return EXIT_FAILURE;
    }

    int last_pos = tokens.size() - 1;
    vector<string> final_ans;
    final_ans.assign(n * 2 + 2, "error");
    str = calculate_postfix_expression(tokens, last_pos, final_ans);
    if (str == "error")
    {
        cout << "Invalid expression." << endl;
        return EXIT_FAILURE;
    }

    print_nums(tokens);
    print_ops(tokens);

    cout << "Result: ";
    for (int i = 0; i < final_ans.size(); i++)
    {
        if (final_ans[i] != "error")
            cout << final_ans[i] << ' ';
    }
    cout << str;
    cout << endl;
    return EXIT_SUCCESS;
}

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_postfix_expression(
    vector<string> &tokens, vector<string> &vector_ans);
void print_ops(const vector<string> &tokens);
void print_nums(const vector<string> &tokens);
void expand(vector<string> &vector_ans, int len);
void prinf_ans(vector<string> &vector_ans);

int main()
{
    int len = 0;
    string input_buffer;
    vector<string> tokens, vector_ans;

    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:";

    if (tokens.size() == 1)
    {
        cout << " " << tokens[0];
    }
    len = tokens.size();
    expand(vector_ans, len);
    calculate_postfix_expression(tokens, vector_ans);
    prinf_ans(vector_ans);

    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;
    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;
                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;
        }
        if (num - op < 1)
        {
            return 0;
        }
    }
    if (num - op != 1)
    {
        return 0;
    }
    return 1;
}

void expand(vector<string> &vector_ans, int len)
{
    for (int i = 0; i < len; i++)
    {
        vector_ans.push_back("\0");
    }
}

string calculate_postfix_expression(
    vector<string> &tokens, vector<string> &vector_ans)
{
    string ans, num_1, num_2, op;
    int location = tokens.size() - 1;
    op = tokens[tokens.size() - 1];
    tokens.pop_back();
    if (op == "+")
    {
        num_2 = calculate_postfix_expression(tokens, vector_ans);
        num_1 = calculate_postfix_expression(tokens, vector_ans);
        ans = to_string(stol(num_1) + stol(num_2));
        vector_ans[location] = ans;
        return ans;
    }
    else if (op == "-")
    {
        num_2 = calculate_postfix_expression(tokens, vector_ans);
        num_1 = calculate_postfix_expression(tokens, vector_ans);
        ans = to_string(stol(num_1) - stol(num_2));
        vector_ans[location] = ans;
        return ans;
    }
    else if (op == "*")
    {
        num_2 = calculate_postfix_expression(tokens, vector_ans);
        num_1 = calculate_postfix_expression(tokens, vector_ans);
        ans = to_string(stol(num_1) * stol(num_2));
        vector_ans[location] = ans;
        return ans;
    }
    else if (op == "/")
    {
        num_2 = calculate_postfix_expression(tokens, vector_ans);
        num_1 = calculate_postfix_expression(tokens, vector_ans);
        ans = to_string(stol(num_1) / stol(num_2));
        vector_ans[location] = ans;
        return ans;
    }
    else
    {
        return op;
    }
}

void prinf_ans(vector<string> &vector_ans)
{
    for (int i = 0; i < vector_ans.size(); i++)
    {
        if (vector_ans[i] != "\0")
        {
            cout << " " << vector_ans[i];
        }
    }
    cout << endl;
}

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(vector<string> &tokens, int &pos);
bool check_postfix_expression(const vector<string> &tokens);
string calculate_postfix_expression(vector<string> &tokens, int &last_pos);
// hint: use std::to_string(long) to convert long to string
// see https://en.cppreference.com/w/cpp/string/basic_string/to_string
// hint: use recursion to find the subexpressions of two operands
void print_ops(const vector<string> &tokens);
void print_nums(const vector<string> &tokens);
void calculate_expression(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_postfix_expression(tokens))
    {
        cout << "Invalid expression." << endl;
        return EXIT_FAILURE;
    }

    print_nums(tokens);

    print_ops(tokens);

    cout << "Result:";
    int last_pos = tokens.size() - 1;
    calculate_expression(tokens);
    cout << endl;

    return EXIT_SUCCESS;
}

bool is_number(string str) // Check if a string is a number
{
    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);
    }
}

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_expression(const vector<string> tokens)
{
    if (tokens.size() == 1)
    {
        cout << tokens[0];
        return;
    }

    vector<long> num_stack;
    int now = 0;
    while (now < tokens.size())
    {
        while (is_number(tokens[now]))
        {
            num_stack.push_back(stol(tokens[now]));
            now++;
        }
        long a = num_stack[num_stack.size() - 2],
             b = num_stack[num_stack.size() - 1];
        num_stack.pop_back();
        num_stack.pop_back();

        if (tokens[now] == "+")
            num_stack.push_back(a + b);
        else if (tokens[now] == "-")
            num_stack.push_back(a - b);
        else if (tokens[now] == "*")
            num_stack.push_back(a * b);
        else if (tokens[now] == "/")
            num_stack.push_back(a / b);

        cout << ' ' << num_stack[num_stack.size() - 1];

        now++;
    }
}

bool check_postfix_expression(const vector<string> &tokens)
{
    int stack_count = 0;

    for (int i = 0; i < tokens.size(); i++)
    {
        if (i > 0 && stack_count < 1)
            return false;
        if (is_number(tokens[i]))
            stack_count++;
        else if (tokens[i] == "+" || tokens[i] == "-" 
                    || tokens[i] == "*" || tokens[i] == "/")
            stack_count--;
        else
            return false;
    }
    return stack_count == 1;
}