表达式求值
利用栈编写表达式求值程序：输入含有“+”、“-”、“*”、“/”四则运算的表达式，其中负数要用（0-正数）表示，并以=结束。要求输出表达式的值（两运算符号的优先关系见教材表3.1）。输入格式
第一行：一个算术表达式
输出格式
第一行：算术表达式的值
输入样例
3*(9-7)=
输出样例
6
不知道为什么输出不了结果
#include<malloc.h>
#include<stdio.h>
#define OK 1
#define ERROR 0
#define STACK_INIT_SIZE 100 // 存储空间初始分配量
#define STACKINCREMENT 10 // 存储空间分配增量
typedef char SElemType; // 定义栈元素类型
typedef int Status; // Status是函数的类型,其值是函数结果状态代码，如OK等
struct SqStack
{
SElemType *base; // 在栈构造之前和销毁之后，base的值为NULL
SElemType *top; // 栈顶指针
int stacksize; // 当前已分配的存储空间，以元素为单位
}; // 顺序栈
Status InitStack(SqStack &S)
{
// 构造一个空栈S，该栈预定义大小为STACK_INIT_SIZE
S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));
if(!S.base) return ERROR;
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
return OK;
}
Status Push(SqStack &S,SElemType e)
{
// 在栈S中插入元素e为新的栈顶元素
if(S.top-S.base>=S.stacksize)
{
S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));
if(!S.base) return ERROR;
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*S.top++=e;
return OK;
}
Status Pop(SqStack &S,SElemType &e)
{
// 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR
if(S.top==S.base) return ERROR;
e=*--S.top;
return OK;
}
Status GetTop(SqStack S,SElemType &e)
{
// 若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR
if(S.top==S.base) return ERROR;
e=*(S.top-1);
return OK;
}
int StackLength(SqStack S)
{
// 返回栈S的元素个数
int i;
i=S.top-S.base;
return i;
}
Status StackTraverse(SqStack S)
{
// 从栈顶到栈底依次输出栈中的每个元素
SElemType *p = (SElemType *)malloc(sizeof(SElemType));
p = S.top;
if(S.top==S.base)printf("The Stack is Empty!");
else
{
printf("The Stack is: ");
p--;
while(p>=S.base)
{
printf("%d ", *p);
p--;
}
}
printf("\n");
return OK;
}
int In(char ch)
{
if(ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch=='('||ch==')')
return 0;
else
return 1;
}
char Precede(char a,char b)
{
char z;
if((b=='+')||(b=='-')||(b=='*')||(b=='/')||(b=='(')||(b==')')||(b=='='))
switch(a)
{
case '+':
case '-':
if((b=='*')||(b=='/')||(b=='('))
z='<';
break;
case '*':
case '/':
if(b=='(')
z='<';
else
z='>';
break;
case '(':
if(b=='=')
z='E';
else if(b==')')
z='=';
else
z='<';
break;
case ')':
if(b=='(')
z='E';
else
z='>';
break;
case '=':
if(b=='=')
z='=';
else if(b==')')
z='E';
else
z='>';
break;
}
else z='E';
return z;
}
char Operate(SElemType a,SElemType thera,SElemType b)
{
switch(thera)
{
case '+':return a+b;
case '-':return a-b;
case '*':return a*b;
case '/':return a/b;
}
}
char expression()
{
SqStack OPND,OPTR;
char ch;
SElemType e,x,thera,a,b;
InitStack(OPTR);
InitStack(OPND);
Push(OPTR,'=');
scanf("%c",&ch);
while(ch!='='||GetTop(OPTR,e)!='=')
{
if(!In(ch))
{
Push(OPND,ch);
scanf("%c",&ch);
}
else
{
switch(Precede(GetTop(OPTR,e),ch))
{
case '<':Push(OPTR,ch);
scanf("%c",&ch);
break;
case '>':Pop(OPTR,thera);
Pop(OPND,b);
Pop(OPND,a);
Push(OPND,Operate(a,thera,b));
break;
case'=':
Pop(OPTR,x);
scanf("%c",&ch);
break;
}
}
}
return GetTop(OPND,e);
}
int main()
{
printf("%c",expression());
}
#include <iostream>
#include <cstring>
#include <algorithm>
#include <stack>
#include <unordered_map>
using namespace std;
stack<int> num;
stack<char> op;
void eval()
{
auto b = num.top(); num.pop();
auto a = num.top(); num.pop();
auto c = op.top(); op.pop();
int x;
if (c == '+') x = a + b;
else if (c == '-') x = a - b;
else if (c == '*') x = a * b;
else x = a / b;
num.push(x);
}
int main()
{
unordered_map<char, int> pr{{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}};
string str;
cin >> str;
for (int i = 0; i < str.size(); i ++ )
{
auto c = str;
if (isdigit(c))
{
int x = 0, j = i;
while (j < str.size() && isdigit(str))
x = x * 10 + str - '0';
i = j - 1;
num.push(x);
}
else if (c == '(') op.push(c);
else if (c == ')')
{
while (op.top() != '(') eval();
op.pop();
}
else
{
while (op.size() && pr >= pr) eval();
op.push(c);
}
}
while (op.size()) eval();
cout << num.top() << endl;
return 0;
} 答案
页:
[1]