364 lines
10 KiB
C++
364 lines
10 KiB
C++
#include <iostream>
|
|
#include <stack>
|
|
#include <string>
|
|
#include <cctype>
|
|
#include <map>
|
|
#include <string.h>
|
|
#include <stdio.h>
|
|
#include <queue>
|
|
#include <algorithm>
|
|
#include <cassert>
|
|
|
|
// 1. Part 1 can create correct post-fix expression from the input
|
|
// (The operators are addition and multiplication.
|
|
// All the operands are positive integers between 1 and 9) (10%)
|
|
|
|
// 2. Part 2 can evaluate the simple post-fix expression correctly
|
|
// (The operators are addition and multiplication,
|
|
// all the operands are positive integers between 1 and 9.
|
|
// In the post-fix expression, all the operands and operators are separated by a “ ”.) (10%)
|
|
|
|
// 3. The operands can be any positive integers. (5%)
|
|
// 4. The operands can be negative integers. (5%)
|
|
// 5. The operands can be float numbers. (5%)
|
|
// 6. The operators can be “-, /, ^, (, )”. (5%)
|
|
|
|
// 2. pseudo code of the algorithm
|
|
// convert to postfix expression use stack,
|
|
// 1. if it is an operand, add to postfix,
|
|
// 2. if it is an operator,
|
|
// 2.1 if it is the first operator, push into `s` stack
|
|
// 2.2 if `s` stack already got element, compare the weight of opreators
|
|
// 2.3 pop `s` stack until the top most one got smaller precedence
|
|
// 3. if it is a bracket, push into stack `s`,
|
|
// 3. if it is a closing bracket, pop all element from `s` stack back to postfix,
|
|
// else return the result
|
|
|
|
/**
|
|
* check if a string is a number
|
|
* @param str_test the string to check
|
|
* @return true if the string is a number, false otherwise
|
|
*/
|
|
bool checkIsNumber(std::string &str_test)
|
|
{
|
|
bool output = true;
|
|
|
|
// check if the string is longer than 1 character
|
|
if (str_test.length() > 1)
|
|
{
|
|
// check each character in the string
|
|
for (auto &c : str_test)
|
|
{
|
|
// if the character is not a digit, a dot or a minus sign
|
|
if (!(('1' <= c && c <= '9') || c == '.' || c == '-'))
|
|
{
|
|
// set the output to false
|
|
output = false;
|
|
// break the loop
|
|
break;
|
|
}
|
|
}
|
|
}
|
|
else
|
|
{
|
|
// if the string is only one character long
|
|
char c = str_test[0];
|
|
// if the character is not a digit
|
|
if (!(('1' <= c && c <= '9')))
|
|
{
|
|
// set the output to false
|
|
output = false;
|
|
}
|
|
}
|
|
|
|
return output;
|
|
}
|
|
|
|
// 1. Part 1 can create correct post-fix expression from the input
|
|
std::queue<std::string> infixToPostfix(const std::string &infix)
|
|
{
|
|
std::queue<std::string> output;
|
|
std::stack<std::string> ss;
|
|
std::queue<std::string> q_postfix;
|
|
std::string postfix_temp;
|
|
std::map<std::string, int> q_precedence = {{"+", 1}, {"-", 1}, {"*", 2}, {"/", 2}, {"(", 0}, {"^", 3}};
|
|
std::stack<char *> sc;
|
|
std::queue<std::string> q;
|
|
|
|
const char s_delimit[2] = " ";
|
|
char *token;
|
|
// seperated by delimiter space
|
|
token = strtok(const_cast<char *>(infix.c_str()), s_delimit);
|
|
while (token != NULL)
|
|
{
|
|
q.push(token);
|
|
token = strtok(NULL, s_delimit);
|
|
}
|
|
|
|
while (!q.empty())
|
|
{
|
|
std::string temp = q.front();
|
|
q.pop();
|
|
|
|
if (checkIsNumber(temp))
|
|
{
|
|
q_postfix.push(temp);
|
|
}
|
|
|
|
// 其實括號入面同括號出面嘅數你當佢兩條式計就得
|
|
else if (temp.compare("(") == 0)
|
|
{
|
|
// 2. if '(', push to stack
|
|
ss.push(temp);
|
|
}
|
|
|
|
// 咁佢呢度關括號呀嘛,
|
|
// 咁佢咪會由個 stack 嗰度 port 返曬啲operator出嚟囉, 1+4*5 變咗 145*+
|
|
// 永遠解開 operator都係會向由左向右
|
|
else if (temp.compare(")") == 0)
|
|
{
|
|
while (!ss.empty() && ss.top() != "(")
|
|
{
|
|
q_postfix.push(ss.top());
|
|
ss.pop();
|
|
}
|
|
|
|
if (!ss.empty())
|
|
ss.pop(); // pop '('
|
|
}
|
|
else
|
|
{
|
|
// 4. if operator, pop operators with greater or equal precedence
|
|
// 比較兩個 operand 之間個先後次序, 數字大嘅計先
|
|
while (!ss.empty() && q_precedence[temp] <= q_precedence[ss.top()])
|
|
{
|
|
q_postfix.push(ss.top());
|
|
ss.pop();
|
|
}
|
|
ss.push(temp); // push current operator
|
|
}
|
|
}
|
|
|
|
// 5. pop last operator
|
|
while (!ss.empty())
|
|
{
|
|
q_postfix.push(ss.top());
|
|
ss.pop();
|
|
}
|
|
|
|
return q_postfix;
|
|
}
|
|
|
|
float evaluatePostfix(std::queue<std::string> &postfix)
|
|
{
|
|
std::stack<float> s;
|
|
std::string element = postfix.front();
|
|
|
|
std::cout << "Corresponding postfix expression: ";
|
|
|
|
while (!postfix.empty())
|
|
{
|
|
// 獨立 pop 番佢出嚟
|
|
std::string element = postfix.front();
|
|
postfix.pop();
|
|
std::cout << element << ' ';
|
|
|
|
if (checkIsNumber(element))
|
|
{ // 1. if operand, push to stack
|
|
s.push(std::stof(element));
|
|
}
|
|
else
|
|
{
|
|
// 如果見到係operator, 攞返嗰兩粒數字出嚟計計佢
|
|
float op2 = s.top();
|
|
s.pop();
|
|
float op1 = s.top();
|
|
s.pop();
|
|
|
|
switch (element[0])
|
|
{
|
|
case '+':
|
|
s.push(op1 + op2);
|
|
break;
|
|
case '-':
|
|
s.push(op1 - op2);
|
|
break;
|
|
case '*':
|
|
s.push(op1 * op2);
|
|
break;
|
|
case '/':
|
|
s.push(op1 / op2);
|
|
break;
|
|
case '^':
|
|
float temp = op1;
|
|
for (float i = 0; i < op2 - 1; i++)
|
|
{
|
|
op1 = op1 * temp;
|
|
}
|
|
s.push(op1);
|
|
break;
|
|
}
|
|
}
|
|
}
|
|
|
|
std::cout << std::endl;
|
|
|
|
return s.top();
|
|
}
|
|
|
|
int main()
|
|
{
|
|
std::queue<std::string> q_temp;
|
|
std::string infix;
|
|
float result = 0;
|
|
|
|
infix = "1 + 2";
|
|
std::cout << "e.g. " << infix << std::endl;
|
|
q_temp = infixToPostfix(infix);
|
|
result = evaluatePostfix(q_temp);
|
|
std::cout << "result: " << result << std::endl;
|
|
assert(result == 3);
|
|
|
|
// 3. The operands can be any positive integers. (5%)
|
|
// 6. The operators can be “-, /, ^, (, )”. (5%)
|
|
infix = "1 + 2 - 3 + 4 - 5 + 6 - 7 + 8 - 9";
|
|
std::cout << "e.g. " << infix << std::endl;
|
|
q_temp = infixToPostfix(infix);
|
|
result = evaluatePostfix(q_temp);
|
|
std::cout << "result: " << result << std::endl;
|
|
assert(result == -3);
|
|
|
|
// 3. The operands can be any positive integers. (5%)
|
|
// 6. The operators can be “-, /, ^, (, )”. (5%)
|
|
infix = "1 + 2 - 3 * 4 / 5 + 6 - 7 * 8 + 9";
|
|
std::cout << "e.g. " << infix << std::endl;
|
|
q_temp = infixToPostfix(infix);
|
|
result = evaluatePostfix(q_temp);
|
|
std::cout << "result: " << result << std::endl;
|
|
assert(std::abs(result - -40.4) < 0.0001);
|
|
|
|
// 4. The operands can be negative integers. (5%)
|
|
infix = "-1 + 2";
|
|
std::cout << "e.g. " << infix << std::endl;
|
|
q_temp = infixToPostfix(infix);
|
|
result = evaluatePostfix(q_temp);
|
|
std::cout << "result: " << result << std::endl;
|
|
assert(result == 1);
|
|
|
|
// 4. The operands can be negative integers. (5%)
|
|
infix = "1 + -2";
|
|
std::cout << "e.g. " << infix << std::endl;
|
|
q_temp = infixToPostfix(infix);
|
|
result = evaluatePostfix(q_temp);
|
|
std::cout << "result: " << result << std::endl;
|
|
assert(result == -1);
|
|
|
|
// 4. The operands can be negative integers. (5%)
|
|
infix = "-1 + -2";
|
|
std::cout << "e.g. " << infix << std::endl;
|
|
q_temp = infixToPostfix(infix);
|
|
result = evaluatePostfix(q_temp);
|
|
std::cout << "result: " << result << std::endl;
|
|
assert(result == -3);
|
|
|
|
// 5. The operands can be float numbers. (5%)
|
|
infix = "1.1 + 2.1";
|
|
std::cout << "e.g. " << infix << std::endl;
|
|
q_temp = infixToPostfix(infix);
|
|
result = evaluatePostfix(q_temp);
|
|
std::cout << "result: " << result << std::endl;
|
|
assert(std::abs(result - 3.2) < 0.001);
|
|
|
|
// 5. The operands can be float numbers. (5%)
|
|
// 4. The operands can be negative integers. (5%)
|
|
infix = "-1.1 + 2.3";
|
|
std::cout << "e.g. " << infix << std::endl;
|
|
q_temp = infixToPostfix(infix);
|
|
result = evaluatePostfix(q_temp);
|
|
std::cout << "result: " << result << std::endl;
|
|
assert(std::abs(result - 1.2) < 0.001);
|
|
|
|
// 5. The operands can be float numbers. (5%)
|
|
infix = "1.1 * 6";
|
|
std::cout << "e.g. " << infix << std::endl;
|
|
q_temp = infixToPostfix(infix);
|
|
result = evaluatePostfix(q_temp);
|
|
std::cout << "result: " << result << std::endl;
|
|
assert(std::abs(result - 6.6) < 0.001);
|
|
|
|
//
|
|
// 6. The operators can be “-, /, ^, (, )”. (5%)
|
|
infix = "1 + 2 ^ 3";
|
|
std::cout << "e.g. " << infix << std::endl;
|
|
q_temp = infixToPostfix(infix);
|
|
result = evaluatePostfix(q_temp);
|
|
std::cout << "result: " << result << std::endl;
|
|
assert(result == 9);
|
|
|
|
//
|
|
// 6. The operators can be “-, /, ^, (, )”. (5%)
|
|
infix = "( 1 + 4 ) * 5";
|
|
std::cout << "e.g. " << infix << std::endl;
|
|
q_temp = infixToPostfix(infix);
|
|
result = evaluatePostfix(q_temp);
|
|
assert(result == 25);
|
|
std::cout << "result: " << result << std::endl;
|
|
|
|
//
|
|
// 6. The operators can be “-, /, ^, (, )”. (5%)
|
|
infix = "( 1 + 4 * 5 ) * 5";
|
|
std::cout << "e.g. " << infix << std::endl;
|
|
q_temp = infixToPostfix(infix);
|
|
result = evaluatePostfix(q_temp);
|
|
assert(result == 105);
|
|
std::cout << "result: " << result << std::endl;
|
|
|
|
//
|
|
// 6. The operators can be “-, /, ^, (, )”. (5%)
|
|
infix = "( 1 + 4 * 5 ) - 2 * 5";
|
|
std::cout << "e.g. " << infix << std::endl;
|
|
q_temp = infixToPostfix(infix);
|
|
result = evaluatePostfix(q_temp);
|
|
assert(result == 11);
|
|
std::cout << "result: " << result << std::endl;
|
|
|
|
//
|
|
// 6. The operators can be “-, /, ^, (, )”. (5%)
|
|
infix = "( 11 + 4 * 5 ) - 6 * 5";
|
|
std::cout << "e.g. " << infix << std::endl;
|
|
q_temp = infixToPostfix(infix);
|
|
result = evaluatePostfix(q_temp);
|
|
assert(result == 1);
|
|
std::cout << "result: " << result << std::endl;
|
|
|
|
//
|
|
// 5. The operands can be float numbers. (5%)
|
|
// 6. The operators can be “-, /, ^, (, )”.
|
|
infix = "( 1.1 + 4 ) * 2";
|
|
std::cout << "e.g. " << infix << std::endl;
|
|
q_temp = infixToPostfix(infix);
|
|
result = evaluatePostfix(q_temp);
|
|
assert(std::abs(result - 10.2) < 0.001);
|
|
std::cout << "result: " << result << std::endl;
|
|
|
|
//
|
|
// 5. The operands can be float numbers. (5%)
|
|
// 6. The operators can be “-, /, ^, (, )”.
|
|
infix = "1 + ( 1 + ( 1 + 2 ^ 3 ) * 3 ^ 2 ) * 2";
|
|
std::cout << "e.g. " << infix << std::endl;
|
|
q_temp = infixToPostfix(infix);
|
|
result = evaluatePostfix(q_temp);
|
|
std::cout << "result: " << result << std::endl;
|
|
assert(std::abs(result - 165) < 0.001);
|
|
|
|
std::cout << "Enter an arithmetic expression: ";
|
|
std::getline(std::cin, infix);
|
|
q_temp = infixToPostfix(infix);
|
|
result = evaluatePostfix(q_temp);
|
|
std::cout << "result: " << result << std::endl;
|
|
|
|
std::cout << "done" << std::endl;
|
|
|
|
return 0;
|
|
}
|