Evaluate expression in infix notation using stack

[JayNg (JayNguyen)]

Em đang có 1 bài tập:

Yêu cầu sử dụng cấu trúc dữ liệu Stack để tính giá trị biểu thức!

Yêu cầu:

• Program cho phép nhập ( { [
• Program cho phép check parentheses is balanced or not
• Print error nếu ##/ 0.0

Ví dụ:
Input:

{10.1+8.4*4.8}/2.2
(19.2-8.6)/[12.4-3.1*4.0]
(10.1*(8.4+4.8)}/2.9
[5.3/2.5+{7.7-3.9*2.6}]*(0.8+30.9)
{5.4/2.4+(7.9-3.2*2.4)}*([2.5+30.1]-{10.6+8.0*4.1}/2.5)
EOI

Output

22.918
Error!: divide by zero
Error!: unbalanced parentheses
-10.144
37.643

Code chạy nhưng ko đúng, em ko biết sai ở đâu nữa, mong mọi người xem giúp em ạ! em cảm ơn ạ!

Bài làm (link online):

#include <stdio.h>
#include <cstdlib>
#include<iostream>
#include<cctype>
#include<cstring>
#include<stack>
#include<cmath>
#include<sstream>
using namespace std;

class DividedByZero: public exception {};

bool is_balanced(const string& parenthesis) // for checking parentheses 
{
    stack<char> store;
    char check;
    for(string::size_type i = 0; i < parenthesis.length(); ++i)
    {
        check = parenthesis[i];
        if(check == '(' || check == '{' || check == '[')
        {
            store.push(check);
        }
        if(!store.empty())
        {
            if(check == ')')
            {
                if(store.top() == '(')
                {
                    store.pop();
                    continue;               
                }
                else
                {
                    break;
                }            
            }
            if(check == '}')
            {
                if(store.top() == '{')
                {
                     store.pop();
                     continue;
                }
                else
                {
                    break;
                }
            }
            if(check == ']')
            {
                if(store.top() == '[')
                {
                     store.pop();
                     continue;
                }
                else
                {
                    break;
                }
            }
        }
        else
            break;
    }   
    return(store.empty());
}

double precedence(char op) // precedence rules of operators
{
    if(op == '+' || op == '-')
        return 1;
    else if(op == '*' || op == '/')
        return 2;
   return 0;        
}

void parse_stack_top(stack<double>& operand, stack<char>& operation) // parse stack top
{
    double number1, number2;
    
    number2 = operand.top();
    operand.pop();
    
    number1 = operand.top();
    operand.pop();
    
    switch(operation.top())
    {
        case '+': operand.push(number1 + number2);
        break;
        
        case '-': operand.push(number1 - number2);
        break;
        
        case '*': operand.push(number1 * number2);
        break;
        
        case '/': 
        if(number2 == 0) // if number2 = 0, can not devide by zero
        {
            cout << "\nError!: Divide by zero.";       
            throw DividedByZero();
        }
        else
            operand.push(number1 / number2);
    }
    operand.pop();
}

double evaluate_stack(const string& token) // evaluate expression
{
    stack<double> operand;
    stack<char> operation;

    for(string::size_type i = 0; i < token.size(); i++)
    {
        if(isdigit(token[i]) || token[i] == '.') // check for numberic, and double value
        {
            double val;
            while(i < token.size() && isdigit(token[i])) // if element of number is larger than one
            {
                val = (val*10) + (token[i]-'0');
                i++;
            }
            i--;          
            operand.push(val);
        }       
        else if(token[i] == '+' || token[i] == '-' || token[i] == '*' || token[i] == '/')
        {
            while(!operation.empty() && precedence(token[i]) < precedence(operation.top()))
            {
                parse_stack_top(operand, operation);
                
            }
            operation.push(token[i]);
        }       
        else if(token[i] == '(' || token[i] == '{' || token[i] == '[')
        {
            operation.push('(');
        }
        
        else if(token[i] == ')' || token[i] == '}' || token[i] == ']')
        {
            while(!operation.empty() && operation.top() != '(' || operation.top() != '{' || operation.top() != '[')
            {
               parse_stack_top(operand, operation);            
            }
            operation.pop();
        }
    }       
    while(!operation.empty())
    {
         parse_stack_top(operand, operation);
    }  
    return operand.top();       
}

int main(int argc, char** argv) {

    string token;
    
    cout << "\nYour Expression: ";
    getline(cin, token);
    
    if(is_balanced(token))
    {
        answer = evaluate_stack(token);
        cout << "\nResult: " << answer;
        
    }
    else
        cout << "\nError!: parentheses is not balanced!";
    
    
    return 0;
}

[JayNg (JayNguyen)]

bài này mai là deadline, bí quá nên em mới mang lên đây để nhờ mg ạ

[Sherly1001]

    if(isdigit(token[i]) || token[i] == '.') // check for numberic, and double value
    {
        double val;
        while(i < token.size() && isdigit(token[i])) // if element of number is larger than one
        {
            val = (val*10) + (token[i]-'0');
            i++;
        }
        i--;          
        operand.push(val);
    }

Trong hàm evaluate_stack() thì cái này không đúng với số thực.

Nó chỉ lấy đến dấu . là hết. Rồi lại push lại ký tự trước dấu . mãi cho đến khi chết máy.

[JayNg (JayNguyen)]

vây em phải sửa đoạn nào ạ?

[Sherly1001]

Mình sửa sương sương giúp bạn nè.

#include <cctype>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <sstream>
#include <stack>
#include <stdio.h>

using namespace std;

class DividedByZero : public exception {};

bool is_balanced(const string &parenthesis) // for checking parentheses
{
    stack<char> store;
    char check;
    for (string::size_type i = 0; i < parenthesis.length(); ++i) {
        check = parenthesis[i];
        if (check == '(' || check == '{' || check == '[') { store.push(check); }
        if (!store.empty()) {
            if (check == ')') {
                if (store.top() == '(') {
                    store.pop();
                    continue;
                } else {
                    break;
                }
            }
            if (check == '}') {
                if (store.top() == '{') {
                    store.pop();
                    continue;
                } else {
                    break;
                }
            }
            if (check == ']') {
                if (store.top() == '[') {
                    store.pop();
                    continue;
                } else {
                    break;
                }
            }
        } else
            break;
    }
    return (store.empty());
}

double precedence(char op) // precedence rules of operators
{
    if (op == '+' || op == '-')
        return 1;
    else if (op == '*' || op == '/')
        return 2;
    return 0;
}

void parse_stack_top(stack<double> &operand, stack<char> &operation) // parse stack top
{
    double number1, number2;

    number2 = operand.top();
    operand.pop();

    number1 = operand.top();
    operand.pop();

    switch (operation.top()) {
    case '+': operand.push(number1 + number2); break;

    case '-': operand.push(number1 - number2); break;

    case '*': operand.push(number1 * number2); break;

    case '/':
        if (number2 == 0) // if number2 = 0, can not devide by zero
        {
            cout << "\nError!: Divide by zero.";
            throw DividedByZero();
        } else
            operand.push(number1 / number2);
    }
    operation.pop();
}

double evaluate_stack(const string &token) // evaluate expression
{
    stack<double> operand;
    stack<char> operation;

    for (string::size_type i = 0; i < token.size(); i++) {
        if (isdigit(token[i]) || token[i] == '.') // check for numberic, and double value
        {
            double val = 0;
            while (i < token.size() && isdigit(token[i])) // if element of number is larger than one
            {
                val = (val * 10) + (token[i] - '0');
                i++;
            }
            if (token[i] == '.') {
                double resp = 0;
                i++;
                int powTen = 10;
                while (i < token.size() && isdigit(token[i])) {
                    resp = resp + double(token[i] - '0') / powTen;
                    powTen *= 10;
                    i++;
                }
                val += resp;
            }
            if (!isdigit(token[i])) i--;
            operand.push(val);
        } else if (token[i] == '+' || token[i] == '-' || token[i] == '*' || token[i] == '/') {
            while (!operation.empty() &&  precedence(token[i]) < precedence(operation.top())) {
                parse_stack_top(operand, operation);
            }
            operation.push(token[i]);
        } else if (token[i] == '(' || token[i] == '{' || token[i] == '[') {
            operation.push('(');
        }

        else if (token[i] == ')' || token[i] == '}' || token[i] == ']') {
            while (!operation.empty() && operation.top() != '(') {
                parse_stack_top(operand, operation);
            }
            operation.pop();
        }
    }
    while (!operation.empty()) { parse_stack_top(operand, operation); }
    return operand.top();
}

int main(int argc, char **argv) {

    string token;

    cout << "\nYour Expression: ";
    getline(cin, token);

    if (is_balanced(token)) {
        cout << "\nResult: " << evaluate_stack(token);

    } else
        cout << "\nError!: parentheses is not balanced!";


    return 0;
}

[JayNg (JayNguyen)]

em cảm ơn anh vì đã sửa cho em ạ! nhưng em run mà nó vẫn ko ra kết quả ạ :(((

cũng ko hiểu sai ở đâu nữa ạ :((

[Sherly1001]

Được mà nhỉ.

Bạn copy nguyên cả chỗ đó nha.

Test result

[JayNg (JayNguyen)]

uầy, code chạy rùi ạ!! em cảm ơn anh nhìu nha anh <3