更新时间:2023-02-18 11:12:12
这基本上是对Yuushi回答的评论.
This is basically a comment to the answer from 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 +
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).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;
}