Pta-7-20 Expression conversion (infix to suffix, parentheses, negative number, decimal conversion)

In this paper, the expression of infix is transformed into suffix expression. Difficult points:

1. A number with a decimal
2. Numbers may have signs of plus or minus

Arithmetic expressions have prefix notation, infix notation, and postfix notation. Everyday arithmetic expressions are infix notation, in which the binary operator is placed between two operands. Please design a program to convert an infix expression to a suffix expression.

The test points in this case are as follows:

Let’s first talk about the idea of affixing suffixes in Ming:

1. Suffixes to suffixes

• Create an operator stack to temporarily store operators, and an array or queue to store postfix expressions

  • Scan the infix expression from left to right, adding the operand to the postfix expression if it encounters one
  • If the op operator is encountered, its priority is compared to that of the operator at the top of the stack
  • Trick: If the op has a higher priority than the top of the stack, the op is pushed onto the stack.
  • If it is lower than or equal to the top of the stack, the operator of the stack is continuously popped into the postfix expression until the op takes precedence over the top of the stack
  • Repeat until the infix expression is scanned, and if there are still elements in the operator stack, pop them in sequence into the postfix expression

• The way parentheses are handled

  • Set the priority of the left parenthesis to lower than + -, but insert directly
  • If a close parenthesis is encountered, it pops directly from the operator stack into the postfix expression until an open parenthesis is encountered

2. Evaluation of postfix expressions

• Scan the postfix expression from left to right, pushing it if it is an operand, or popping two operands in a row if it is an operator.
• The operator operation is then performed until the suffix expression is scanned, at which point there is only one element left in the result stack, which is the result of the operation

So let’s go back to our problem, which is as long as we change the infix to the suffix first, so we can save it as a string instead of calculating the value of each position.

The complete code and comments are as follows:

/* Author: Veeupup
#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <map>
using namespace std;

vector<string> ans;
map<char.int> priority;
string operators = "+ - * / ()";    // Save all calculation symbols

void trans(string str) 
{
    stack<char> ops;
    ops.push(The '#');
    string tempStr;
    for (int i = 0; i < str.size(a); i++) {// Check if it is a signed number
        // 1. If I =0 and the character preceding it is an operator,
        // 2. The current character is a number
        if( ((str[i] == The '-' || str[i] == '+') && (i == 0 || string("+ - / * (").find(str[i- 1])! =string::npos)) ||isdigit(str[i]) ) 
        {   // add the operand to the postfix
            // If it is a positive sign, do not add it, either the negative sign or the number itself should be addedtempStr = str[i] ! ='+' ? str.substr(i, 1) : "";
            while (i + 1 < str.size() && operators.find(str[i+1]) == string::npos)
            {
                tempStr += str[++i];
            }
            ans.push_back(tempStr);
        }else { // The occurrence operator
            if(str[i] == '(') 
                ops.push(str[i]);
            else if(str[i] == ') ') {
                while (ops.top() != '(')
                {
                    ans.push_back(string(1, ops.top()));
                    ops.pop(a); } ops.pop(a); }else {
                while (priority[str[i]] <= priority[ops.top()])
                {
                    ans.push_back(string(1, ops.top()));
                    ops.pop(a); } ops.push(str[i]); }}}while (ops.size(a) >1)
    {
        ans.push_back(string(1, ops.top()));
        ops.pop();
    }
}

int main(a)
{
    priority[The '*'] = priority['/'] = 3;
    priority['+'] = priority[The '-'] = 2;
    priority['('] = 1;
    priority[The '#'] = 0;
    string str;
    getline(cin, str);
    trans(str);
    for (int i = 0; i < ans.size(a); i++) cout << (i ?"" : "") << ans[i]; 
    return 0;
}
Copy the code

The way ahead is so long without ending, yet high and low I’ll search with my will unbending.