Parse Mathematical Expressions in a C++ String?
To parse the mathematical expression from a string, we can use the infix to postfix conversion and then evaluate the expression. It is a fast and efficient method that considers the priority of the operator, type of operand, etc. into the consideration.
Approach
- Initialize two stacks. One for storing operands (numbers) and the other for storing operators.
- Go through the mathematical expression token by token separated by spaces.
- If the token is empty, skip it.
- If the token is a number, convert it to a double and push it onto the operand stack.
- If the token is an operator, while the operator stack is not empty and the top operator has equal or higher precedence, pop two operands and one operator, apply the operator to the operands, and push the result back onto the operand stack. Then, push the current operator onto the operator stack.
- Check for parentheses: If the token is an opening parenthesis, push it onto the operator stack. If the token is a closing parenthesis, while the operator stack is not empty and the top operator is not an opening parenthesis, pop two operands and one operator, apply the operator to the operands, and push the result back onto the operand stack. Then, pop the opening parenthesis from the operator stack.
- Perform remaining operations: After parsing the expression, if there are still operators in the operator stack, continue performing operations until the operator stack is empty. For each operation, pop two operands and one operator, apply the operator to the operands, and push the result back onto the operand stack.
- Return the result: The final result of the expression should be at the top of the operand stack.
C++ Progam to Parse Mathematical Expressions
// C++ Program to illustrate how to evalauate a mathematical
// expression that is stored as string
#include <cctype>
#include <cmath>
#include <iostream>
#include <sstream>
#include <stack>
#include <string>
using namespace std;
// Function to check if a character is an operator
bool isOperator(char c)
{
// Returns true if the character is an operator
return c == '+' || c == '-' || c == '*' || c == '/'
|| c == '^';
}
// Function to get the precedence of an operator
int precedence(char op)
{
// Returns the precedence of the operator
if (op == '+' || op == '-')
return 1;
if (op == '*' || op == '/')
return 2;
if (op == '^')
return 3;
return 0;
}
// Function to apply an operator to two operands
double applyOp(double a, double b, char op)
{
// Applies the operator to the operands and returns the
// result
switch (op) {
case '+':
return a + b;
case '-':
return a - b;
case '*':
return a * b;
case '/':
return a / b;
case '^':
return pow(a, b);
default:
return 0;
}
}
// Function to parse and evaluate a mathematical expression
double evaluateExpression(const string& expression)
{
stack<char> operators; // Stack to hold operators
stack<double> operands; // Stack to hold operands
stringstream ss(expression); // String stream to parse
// the expression
string token;
while (getline(
ss, token,
' ')) { // Parse the expression token by token
if (token.empty())
continue; // Skip empty tokens
if (isdigit(token[0])) { // If the token is a number
double num;
stringstream(token)
>> num; // Convert the token to a number
operands.push(num); // Push the number onto the
// operand stack
}
else if (isOperator(token[0])) { // If the token is
// an operator
char op = token[0];
// While the operator stack is not empty and the
// top operator has equal or higher precedence
while (!operators.empty()
&& precedence(operators.top())
>= precedence(op)) {
// Pop two operands and one operator
double b = operands.top();
operands.pop();
double a = operands.top();
operands.pop();
char op = operators.top();
operators.pop();
// Apply the operator to the operands and
// push the result onto the operand stack
operands.push(applyOp(a, b, op));
}
// Push the current operator onto the operator
// stack
operators.push(op);
}
else if (token[0] == '(') { // If the token is an
// opening parenthesis
// Push it onto the operator stack
operators.push('(');
}
else if (token[0] == ')') { // If the token is a
// closing parenthesis
// While the operator stack is not empty and the
// top operator is not an opening parenthesis
while (!operators.empty()
&& operators.top() != '(') {
// Pop two operands and one operator
double b = operands.top();
operands.pop();
double a = operands.top();
operands.pop();
char op = operators.top();
operators.pop();
// Apply the operator to the operands and
// push the result onto the operand stack
operands.push(applyOp(a, b, op));
}
// Pop the opening parenthesis
operators.pop();
}
}
// While the operator stack is not empty
while (!operators.empty()) {
// Pop two operands and one operator
double b = operands.top();
operands.pop();
double a = operands.top();
operands.pop();
char op = operators.top();
operators.pop();
// Apply the operator to the operands and push the
// result onto the operand stack
operands.push(applyOp(a, b, op));
}
// The result is at the top of the operand stack
return operands.top();
}
int main()
{
string expression = "3 + 4 * 2";
// Evaluate the expression
double result = evaluateExpression(expression);
// Print the result
cout << "Result: " << result << endl;
return 0;
}
Output
Result: 11
Time Complexity: O(N), where N is the length of the string.
Auxiliary Space: O(N)
How to Parse Mathematical Expressions in a C++ String?
In C++, strings are sequences of characters stored in a char array. Strings are used to store words and text. We can also store mathematical expressions in this string. In this article, we will explore how to parse mathematical expressions in a C++ String.
Example:
Input:
expression = (3 + 4) * 2 / (1 + 1)
Output:
7