且构网

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

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

更新时间:2023-02-18 12:52:08

这基本上是对Yuushi答案的评论。

This is basically a comment to the answer from Yuushi.


  • 外部while(!stack.empty())循环是错误的。只是删除它。 (保持c的循环体)。在函数结束时,检查堆栈是否为空,否则表达式有语法错误。

  • 由于Yuushi已经说过优先函数看起来是假的。首先你应该给参数更好的名称:一个是操作符到左边,另一个是右边。 (现在你叫它优先(rightOp,leftOp))。然后你应该记录结果的意思 - 现在你返回true如果一个rOp b lOp c ==(a rOp b)lOp c (是的,操作顺序doesn'例如,两个订单中的+和 - 不相同)。

  • 如果您发现一个新运算符,您需要循环使用旧运算符堆栈,例如在读取 a - b * c 后,您的输出为 abc ,堆栈为 [ - *] 。现在你读一个 + ,你需要弹出两个运算符,导致 a b c * - 。即,输入 a - b * c + d 应导致 abc * - 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) << "'\n";
    }

    return 0;
}