Reg*_*bar 9 c++ stack infix-notation postfix-notation
我的讲师给了我一个创建程序来转换和使用Stacks将表达式转换为postfix的任务.我已经制作了堆栈类和一些函数来读取中缀表达式.
但是这个函数被称为convertToPostfix(char * const inFix, char * const postFix)负责将数组inFix中的inFix表达式转换为使用堆栈的postFix数组中的post fix表达式,并没有做它想做的事情.你能帮助我,告诉我我做错了什么吗？
以下是从inFix转换为postFix的函数的代码,convertToPostfix(char * const inFix, char * const postFix)是我需要帮助修复的代码:
void ArithmeticExpression::inputAndConvertToPostfix()
{
char inputChar; //declaring inputChar
int i = 0; //inizalize i to 0
cout << "Enter the Arithmetic Expression(No Spaces): ";
while( ( inputChar = static_cast<char>( cin.get() ) ) != '\n' )
{
if (i >= MAXSIZE) break; //exits program if i is greater than or equal to 100
if(isdigit(inputChar) || isOperator(inputChar))
{
inFix[i] = inputChar; //copies each char to inFix array
cout << inFix[i] << endl;
}
else
cout << "You entered an invalid Arithmetic Expression\n\n" ;
}
// increment i;
i++;
convertToPostfix(inFix, postFix);
}
bool ArithmeticExpression::isOperator(char currentChar)
{
if(currentChar == '+')
return true;
else if(currentChar == '-')
return true;
else if(currentChar == '*')
return true;
else if(currentChar == '/')
return true;
else if(currentChar == '^')
return true;
else if(currentChar == '%')
return true;
else
return false;
}
bool ArithmeticExpression::precedence(char operator1, char operator2)
{
if ( operator1 == '^' )
return true;
else if ( operator2 == '^' )
return false;
else if ( operator1 == '*' || operator1 == '/' )
return true;
else if ( operator1 == '+' || operator1 == '-' )
if ( operator2 == '*' || operator2 == '/' )
return false;
else
return true;
return false;
}
void ArithmeticExpression::convertToPostfix(char * const inFix, char * const postFix)
{
Stack2<char> stack;
const char lp = '(';
stack.push(lp); //Push a left parenthesis ‘(‘ onto the stack.
strcat(inFix,")");//Appends a right parenthesis ‘)’ to the end of infix.
// int i = 0;
int j = 0;
if(!stack.isEmpty())
{
for(int i = 0;i < 100;){
if(isdigit(inFix[i]))
{
postFix[j] = inFix[i];
cout << "This is Post Fix for the first If: " << postFix[j] << endl;
i++;
j++;
}
if(inFix[i] == '(')
{
stack.push(inFix[i]);
cout << "The InFix was a (" << endl;
i++;
//j++;
}
if(isOperator(inFix[i]))
{
char operator1 = inFix[i];
cout << "CUrrent inFix is a operator" << endl;
if(isOperator(stack.getTopPtr()->getData()))
{
cout << "The stack top ptr is a operator1" << endl;
char operator2 = stack.getTopPtr()->getData();
if(precedence(operator1,operator2))
{
//if(isOperator(stack.getTopPtr()->getData())){
cout << "The stack top ptr is a operato2" << endl;
postFix[j] = stack.pop();
cout << "this is post fix " << postFix[j] << endl;
i++;
j++;
// }
}
}
else
stack.push(inFix[i]);
// cout << "Top Ptr is a: "<< stack.getTopPtr()->getData() << endl;
}
for(int r = 0;r != '\0';r++)
cout << postFix[r] << " ";
if(inFix[i] == ')')
{
while(stack.stackTop()!= '(')
{
postFix[j] = stack.pop();
i++;
j++;
}
stack.pop();
}
}
}
}
注意使用此算法生成convertToPostfix函数:
堆栈不为空时,从左到右读取中缀并执行以下操作:
如果中缀中的当前字符是运算符,
这基本上是对Yuushi答案的评论.
precedence(rightOp, leftOp)).然后你应该记录结果意味着什么 - 现在你返回true如果a rOp b lOp c == (a rOp b) lOp c(是的,运营商订单与你所说的不匹配 - "+"和" - "在两个订单中都不相同).a - b * c输出后a b c,堆栈就是[- *].现在你读了一个+,你需要弹出两个运算符,结果a b c * -.即,输入a - b * c + d应该导致a b c * - d +更新:附加完整解决方案(基于Yuushi的答案):
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;
}
所以你的代码存在很多问题。我将发布（应该是）正确的解决方案，其中包含大量注释来解释发生的情况以及您在哪里犯了错误。前面有几件事：
\n\n我将使用std::string而不是char *因为它使事情变得更加干净，老实说，您应该使用它，C++除非您有充分的理由不这样做（例如与C库的互操作性）。该版本还返回 astring而不是将 achar *作为参数。
我使用的是标准库中的堆栈，<stack>它与您自制的堆栈略有不同。top()显示下一个元素而不将其从堆栈中删除，并pop()返回void，但从堆栈中删除顶部元素。
它是一个自由函数，不是类的一部分，但应该很容易修改 - 对我来说，通过这种方式进行测试更容易。
我不相信你的运算符优先级表是正确的，但是，我会让你仔细检查一下。
#include <stack>\n#include <cctype>\n#include <iostream>\n\nstd::string convertToPostfix(std::string& infix)\n{\n std::string postfix; //Our return string\n std::stack<char> stack;\n stack.push('('); //Push a left parenthesis \xe2\x80\x98(\xe2\x80\x98 onto the stack.\n infix.push_back(')');\n\n //We know we need to process every element in the string,\n //so let's do that instead of having to worry about\n //hardcoded numbers and i, j indecies\n for(std::size_t i = 0; i < infix.size(); ++i) {\n\n //If it's a digit, add it to the output\n //Also, if it's a space, add it to the output \n //this makes it look a bit nicer\n if(isdigit(infix[i]) || isspace(infix[i])) {\n postfix.push_back(infix[i]);\n }\n\n //Already iterating over i, so \n //don't need to worry about i++\n //Also, these options are all mutually exclusive,\n //so they should be else if instead of if.\n //(Mutually exclusive in that if something is a digit,\n //it can't be a parens or an operator or anything else).\n else if(infix[i] == '(') {\n stack.push(infix[i]);\n }\n\n //This is farily similar to your code, but cleaned up. \n //With strings we can simply push_back instead of having\n //to worry about incrementing some counter.\n else if(isOperator(infix[i]))\n {\n char operator1 = infix[i];\n if(isOperator(stack.top())) {\n while(!stack.empty() && precedence(operator1,stack.top())) {\n postfix.push_back(stack.top());\n stack.pop();\n }\n }\n //This shouldn't be in an else - we always want to push the\n //operator onto the stack\n stack.push(operator1);\n } \n\n //We've hit a right parens - Why you had a for loop\n //here originally I don't know\n else if(infix[i] == ')') {\n //While top of stack is not a right parens\n while(stack.top() != '(') {\n //Insert into postfix and pop the stack\n postfix.push_back(stack.top());\n stack.pop();\n }\n // Discard the left parens - you'd forgotten to do this\n stack.pop(); \n }\n }\n\n //Remove any remaining operators from the stack\n while(!stack.empty()) {\n postfix.push_back(stack.top());\n stack.pop();\n }\n}\n| 归档时间： |
|
| 查看次数： |
51802 次 |
| 最近记录： |