且构网

分享程序员开发的那些事...
且构网 - 分享程序员编程开发的那些事

使用堆栈从中缀表达式转换为后缀 (C++)

更新时间:2023-02-18 11:12:12

这基本上是对Yuushi回答的评论.

This is basically a comment to the answer from Yuushi.

  • 外部 while(!stack.empty()) 循环是错误的.只需将其删除.(保持c的循环体).在函数结束时,检查堆栈是否为空,否则表达式有语法错误.
  • 正如 Yuushi 已经说过的,优先功能看起来很假.首先你应该给参数起一个更好的名字:一个是左边的操作符,另一个是右边的.(现在你称之为 precedence(rightOp, leftOp)).然后你应该记录结果的含义 - 现在你返回 true if a rOp b lOp c == (a rOp b) lOp c (是的,操作员的顺序与你所说的不匹配 -例如,两个顺序中的+"和-"不一样).
  • 如果你找到一个新的操作符,你需要遍历堆栈中的旧操作符,例如在读取 a - b * c 之后你的输出是 abc 并且堆栈是 [- *].现在你读到了一个+,你需要弹出两个操作符,结果是a b c * -.即,输入 a - b * c + d 应该导致 a b c * - d +
  • The outer while(!stack.empty()) loop is wrong. just remove it. (keep the loop body ofc). At the end of the function, check that the stack is empty, else the expression had syntax errors.
  • As Yuushi already said the precedence function looks bogus. First you should give the parameters better names: one is the operator to the left, and the other to the right. (Right now you call it precedence(rightOp, leftOp)). Then you should document what the result means - right now you return true if a rOp b lOp c == (a rOp b) lOp c (yes, the operator order doesn't match what you call - "+" and "-" are not the same in both orders for example).
  • If you find a new operator you need to loop over the old operators on the stack, for example after reading a - b * c your output is a b c and the stack is [- *]. now you read a +, and you need to pop both operators, resulting in a b c * -. I.e., the input a - b * c + d should result in a b c * - d +

更新:附加完整解决方案(基于 Yuushi 的回答):

Update: appended complete solution (based on Yuushi's answer):

bool isOperator(char currentChar)
{
    switch (currentChar) {
    case '+':
    case '-':
    case '*':
    case '/':
    case '^':
    case '%':
        return true;
    default:
        return false;
    }
}

// returns whether a `lOp` b `rOp` c == (a `lOp` b) `rOp` c
bool precedence(char leftOperator, char rightOperator)
{
    if ( leftOperator == '^' ) {
        return true;
    } else if ( rightOperator == '^' ) {
        return false;
    } else if ( leftOperator == '*' || leftOperator == '/' || leftOperator == '%' ) {
        return true;
    } else if ( rightOperator == '*' || rightOperator == '/' || rightOperator == '%' ) {
        return false;
    }

    return true;
}

#include <stdexcept>
#include <cctype>
#include <sstream>
#include <stack>
std::string convertToPostfix(const std::string& infix)
{
    std::stringstream postfix; // Our return string
    std::stack<char> stack;
    stack.push('('); // Push a left parenthesis ‘(‘ onto the stack.

    for(std::size_t i = 0, l = infix.size(); i < l; ++i) {
        const char current = infix[i];

        if (isspace(current)) {
            // ignore
        }
        // If it's a digit or '.' or a letter ("variables"), add it to the output
        else if(isalnum(current) || '.' == current) {
            postfix << current;
        }

        else if('(' == current) {
            stack.push(current);
        }

        else if(isOperator(current)) {
            char rightOperator = current;
            while(!stack.empty() && isOperator(stack.top()) && precedence(stack.top(), rightOperator)) {
                postfix << ' ' << stack.top();
                stack.pop();
            }
            postfix << ' ';
            stack.push(rightOperator);
        }

        // We've hit a right parens
        else if(')' == current) {
            // While top of stack is not a left parens
            while(!stack.empty() && '(' != stack.top()) {
                postfix << ' ' << stack.top();
                stack.pop();
            }
            if (stack.empty()) {
                throw std::runtime_error("missing left paren");
            }
            // Discard the left paren
            stack.pop();
            postfix << ' ';
        } else {
            throw std::runtime_error("invalid input character");
        }
    }


    // Started with a left paren, now close it:
    // While top of stack is not a left paren
    while(!stack.empty() && '(' != stack.top()) {
        postfix << ' ' << stack.top();
        stack.pop();
    }
    if (stack.empty()) {
        throw std::runtime_error("missing left paren");
    }
    // Discard the left paren
    stack.pop();

    // all open parens should be closed now -> empty stack
    if (!stack.empty()) {
        throw std::runtime_error("missing right paren");
    }

    return postfix.str();
}

#include <iostream>
#include <string>
int main()
{
    for (;;) {
        if (!std::cout.good()) break;
        std::cout << "Enter the Arithmetic Expression: ";
        std::string infix;
        std::getline(std::cin, infix);
        if (infix.empty()) break;

        std::cout << "Postfix: '" << convertToPostfix(infix) << "'
";
    }

    return 0;
}